#11 정수론 - 이항 계수(Binomial Coefficient)

 순서를 고려하지 않고 n개의 물건중 k개를 고르는 경우의 수(조합)를 이항 계수라 한다.  코딩테스트에 이항계수를 구하라는 문제가 나오지는 않겠지만 이항계수를 구해야 해결 가능한 문제가 나올 수는 있기 때문에 이항계수를 구하는 방법들에 대해 한번 따로 정리를 해두기로 한다.

 

1. 이항계수의 수식에 따른 방법

 이항계수를 nCk 를 구하는 수식은 nCk = n!/(k! * (n-k)!)  이다.  n과 k가 입력됐을 때 단순히 이 수식대로 계산하더라도 상당히 빠른 속도로 이항계수를 구할 수 있다.  주의할 점이라면 C나 Java 등의 변수의 자료형에 따른 정수 표현의 한계가 있는 언어의 경우 숫자가 빠르게 커지면서 오버플로우가 발생할 수 있다는 점이다.  그 때문에 이항계수를 구해야하는 문제들은 보통 매우 큰 소수로 모듈러연산을 한 결과를 요구한다.  

 

이 방식으로 이항계수 문제(https://www.acmicpc.net/problem/11050)를 해결한 코드는 다음과 같다.

import sys

input = sys.stdin.readline


def sol11050():
    n, k = map(int, input().split())
    deno = nume = 1
    for i in range(1, k+1):
        deno *= (n-i+1)
        nume *= i
    return deno//nume


if __name__ == '__main__':
    print(sol11050())

 

 

 

2. 동적계획법을 사용한 방법

 이항계수 nCk 는 n개중 k개를 고르는 경우의 수이며 이는 임의의 한개를 고르지 않았다고 가정하고 n-1개중 다시 k개를 고르는 경우의 수와 한개를 이미 골랐다고 가정하고 n-1개중 나머지 k-1개를 고르는 경우의 수를 더한 것과 같다.

즉, nCk = n-1Ck + n-1Ck-1 이라는 점화식이 성립한다.  이 점화식을 기반으로 동적계획법을 사용하면 O(N^2)의 시간/공간 복잡도로 이항계수를 구할 수 있다.  1번 방법에 비해 빠르지는 않지만 중간중간 모듈러연산을 적용하여 오버플로우가 발생할 위험을 조기에 방지할 수 있다.

 

이 방식으로 이항계수 문제(https://www.acmicpc.net/problem/11051)를 해결한 코드는 다음과 같다.

import sys

input = sys.stdin.readline


def sol11051():
    n, k = map(int, input().split())
    c = [[0] * (n+1) for _ in range(n+1)]
    for i in range(n+1):
        c[i][0] = c[i][i] = 1
       
    for i in range(1, n+1):
        for j in range(1, i+1):
            c[i][j] = (c[i-1][j] + c[i-1][j-1]) % 10007
    return c[n][k]


if __name__ == '__main__':
    print(sol11051())

 

 

3. 페르마의 소정리를 이용한 방법

 여기서부터는 조금 복잡하다.  여기서도 마찬가지로 1번 방법에서 사용한 이항계수를 구하기 위한 수식에 페르마의 소정리를 적용하여 풀어나간다. 페르마의 소정리란 p가 소수일 때,  a^p 와 a 는 p로 나눈 나머지가 서로 같다는 정리이다. 수식의 전개는 아래와 같다.

 

nCk % p

= (n!/(k! * (n-k)!)) % p 

= (n! * (k! * (n-k)!) ^ -1) % p

= ((n! % p) * ((k! * (n-k)!)^-1) % p) % p

 

페르마의 소정리 a^p ≡ a (mod p) 에서 양 변에 a^-2를 곱해주면  a^(p-2) ≡ a^-1 (mod p) 이 된다.

∴ ((n! % p) * ((k! * (n-k)!)^-1) % p) % p

= ((n! % p) * ((k! * (n-k)!)^(p-2) % p) % p

= (n! * (k! * (n-k)!)^(p-2)) % p

 

즉, n! 과 (k! * (n-k)!)^(p-2)를 곱한 뒤 p의 나머지를 취하면 이항계수에 p의 나머지를 취한 것과 같은 값이 나온다.

 

 

※ 여기서 하나 더 문제가 있는데, p는 상당히 큰 소수인 경우가 대부분이기 때문에 이 방법을 사용하려면

   거듭제곱을 빠르게 구하는 법도 알아둘 필요가 있다.  n의 k제곱은 n의 k//2제곱의 제곱을 구한 뒤,

   k가 홀수일 경우 n을 한번 더 곱해준 값과 같다.

   ∴ n^k = (n^(k//2)) ^ 2 * n^(k%2) 

   이 방식을 재귀적으로 적용하여 n^k 를 구하면 시간복잡도가 O(K) 에서 O(logK)로 격감한다.

 

이 방식을 사용하여 이항 계수 문제(https://www.acmicpc.net/problem/11401)를 해결한 코드는 다음과 같다.

 

import sys

input = sys.stdin.readline
mod = 1000000007


def sol11401():
    n, k = map(int, input().split())
    if k > n//2:
        k = n-k
    A = fact(n)
    B = pow(fact(k) * fact(n - k), mod - 2)
    return A * B % mod


def pow(a, b):
    if b == 0:
        return 1
    res = pow(a, b // 2) ** 2 % mod
    if b % 2 == 1:
        res = (res * a) % mod
    return res
   
  
def fact(n):
    res = 1
    for i in range(1, n+1):
        res = (res * i) % mod
    return res


if __name__ == '__main__':
    print(sol11401())

위 코드에서는 설명한 수식을 그대로 구현하기 위해 위와같이 코드를 작성했지만 사실 n!, (k! * (n-k)!)^(p-2) 를 구하기보다는 n! / (n-k)! 과 (k!)^(p-2)를 구하는 편이 훨씬 빠르게 문제를 해결할 수 있다.  그 방식으로 작성한 코드는 다음과 같다.

import sys

input = sys.stdin.readline
mod = 1000000007


def sol11401():
    n, k = map(int, input().split())
    if k > n//2:
        k = n-k
    A = fact(n-k+1, n)
    B = pow(fact(1, k), mod - 2)
    return A * B % mod


def pow(a, b):
    if b == 0:
        return 1
    res = pow(a, b // 2) ** 2 % mod
    if b % 2:
        return res * a % mod
    return res
   
  
def fact(a, b):
    res = 1
    for i in range(a, b+1):
        res = (res * i) % mod
    return res


if __name__ == '__main__':
    print(sol11401())