[Algorithm] 정수론 및 조합론(백준 2981,2004번)

백준 알고리즘을 풀면서 각 단계를 마칠 때마다
해당 단계에서 배운 점을 정리해 보면 좋을 것 같아서
복습 겸 풀었던 단계들을 먼저 정리해 보려고 한다.

정수론

정수론에서는 최소 공배수, 최대 공약수에 대한 개념이 주로 나왔던 것 같다.

최대 공약수를 유클리드 호제법이라는 알고리즘을 사용해 구하면 시간 복잡도를 O(N)에서 O(logN)으로 줄일 수 있다.

 

10과 12의 최대 공약수를 구한다고 해보자.

위와 같이 쉽게 구할 수 있다.

코드로 나타내면 아래와 같다.

def gcd(a,b):
    while b:
        a,b=b,a%b
    return a

 

최소 공배수는 최대 공약수를 이용하면 바로 구할 수 있다.

두 수의 곱을 최대 공약수로 나누면 최소 공배수이다.

 

코드로 나타내면 아래와 같다.

def lcm(a,b):
    return a*b//gcd(a,b)

 

정수론에서 가장 내가 어려웠던 문제는 2981번이었다.

2981번: 검문

수식을 통해서 도출해내야 하는 문제였다.

위처럼 수들은 공통적인 나머지와 나누는 수를 가진다.(몫만 다름)

따라서 오른쪽처럼 정리하면, 각 수의 차는 나누는 수를 공약수로 가진다는 것을 알 수 있다.

 

이를 이용해 크기가 가장 큰 나누는 수를 구한 후

나누는 수의 약수들 또한 공약수일 것이기 때문에 약수를 모두 구해주면 된다.

 

코드로 나타내면 아래와 같다.

import sys
input=sys.stdin.readline
def gcd(a,b):
    while b:
        a,b=b,a%b
    return a

count=int(input())
l=sorted(int(input()) for _ in range(count))
newL=[]
for i in range(len(l)-1):
    newL.append(l[i+1]-l[i])
GCD = newL[0]
for idx in range(1, len(newL)):
    GCD = gcd(GCD, newL[idx])
result = set()
for i in range(2, int(GCD**0.5) + 1):
    if GCD % i == 0:
        result.add(i)
        result.add(GCD // i)
result.add(GCD)
print(*sorted(list(result)))

---

조합론

조합론 부분에서는 이항계수에 대한 문제가 주로 나왔다.

이항계수 nCk는 n개 중 k개만큼 순서없이 뽑는 조합의 개수를 말한다.

 

공식은 아래와 같다.

nCk=n!/(n-k)!*k! (0<=k<=n)

이를 파이썬 코드로 나타내보자.

def factorial(n):
    result=1
    for i in range(2,n+1):
        result*=i
    return result

def bino_coef(n,k):
    return factorial(n)//factorial(n-k)//factorial(k)

이렇게 간단하게 이항계수를 구할 수 있다.

 

조합론에서 내가 제일 어려웠던 문제는 2004번이다.

2004번: 조합 0의 개수

처음에는 삽질을 많이 했지만,

0의 개수를 구하는 문제이므로 2와 5의 개수만을 고려하면 됐다.

이항계수의 공식에서 2와 5의 개수를 각각 구하고 최솟값을 구하면 0의 개수를 구할 수 있다.

 

파이썬 코드로 나타내면 다음과 같다.

import sys
input=sys.stdin.readline
def get5count(n):
    count=0
    while n!=0:
        n//=5
        count+=n
    return count
def get2count(n):
    count=0
    while n!=0:
        n//=2
        count+=n
    return count

n,m=map(int,input().split())
print(min(get2count(n)-get2count(n-m)-get2count(m),get5count(n)-get5count(n-m)-get5count(m)))

---

참고

[조합론] 이항계수 알고리즘 3가지

마치며

단계별 알고리즘을 풀면서 

다 해결한 단계를 계속해서 기록해야겠다.

 

잘못된 정보에 대한 피드백은 환영입니다.

감사합니다.