[Algorithm] 이항계수

이항계수

조합론에서 이항계수는 이항식을 이항 정리로 전개했을 때 각 항의 계수이다. 각 항의 계수는 주어진 크기에서 순서없는 조합의 가짓수이다. 

출처: https://rh-tn.tistory.com/32

이항계수는 위와 같다. 이때 이항계수는 nCk나 C(n, k)로 쓰기도 한다. 

 

이항계수는 위의 공식을 사용하여 factorial을 사용해 구할 수도 있고 파스칼의 삼각형을 이용한 동적계획법 알고리즘으로 구할 수 있다.

 

파스칼의 삼각형

출처: https://rh-tn.tistory.com/32

이항계수만을 작성해보면 다음과 같이 삼각형의 형태로 작성할 수 있다. 여기서 이항계수간의 관계를 발견할 수 있다.

nCk = n-1Ck-1 + n-1Ck

위와같은 점화식이 성립한다. 파스칼의 삼각형을 이용하여 다이나믹프로그래밍의 메모이제이션 방식으로 쉽게 이항계수를 구할 수 있다. 

 

Python

다이나믹 프로그래밍 방식 >

import sys
n, k = map(int, sys.stdin.readline().split())
dp = [[0 for _ in range(n+1)] for _ in range(n+1)]

for i in range(n+1):
    for j in range(n+1):
        if j == 0:
            dp[i][j] = 1
        elif i == j:
            dp[i][j] = 1
        elif j == 1:
            dp[i][j] = i
        elif n >= k:
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
print(dp[n][k]) #nCk