Binomial Coefficients

개요

이항 계수(Binomial Coefficients)는 동적 프로그래밍의 고전적인 응용 중 하나이다. 이항 계수는 수학적으로 아래와 같이 정의된다:

 $(\binom{n}{k}) =$  "n개 중에서 k개를 선택하는 방법의 수"

이항 계수는 흔히 조합(combination)이라고 불리며, 다양한 분야에 활용된다. 예를 들어 n명의 사람 중 k명을 뽑는 경우의 수이나, n $\times$ m 격자의 왼쪽 위에서 오른쪽 아래까지, 오른쪽 또는 아래로만 이동할 수 있을 때 가능한 경로의 수^[1]를 구할 때 사용된다. 이 외에도 경로 문제, 선택 문제, 확률 계산 등 매우 다양한 문제에 등장한다.

이항 계수는 동적 프로그래밍의 전형적인 예시 중 하나이다. 왜냐하면 이항 계수는 반복되는 하위 문제 구조를 갖고 있기 때문이다. 이항 계수는 아래와 같이 계산된다:

 $(\binom{n}{k}) = \frac{n!}{(n - k)! k!}$

즉, 팩토리얼을 이용하여 직접 계산할 수 있다. 하지만 이는 중간 계산에서 오버플로(overflow)가 발생한 우려가 있다. 예를 들어, $20! = 2, 432, 902, 008, 176, 640, 000$ 이므로 중간 계산이 너무 커져서 자료형이 감당하지 못한다. 따라서 직접 팩토리얼 계산보다는 점화식을 이용하는 방법이 더 안전하고 효율적이다.

Pascal’s Triangle

파스칼의 삼각형은 figure 2와 같은 형태를 가지고 있는 수의 배치인데, 이항 계수를 삼각형 모양으로 배열한 것이다. 파스칼의 삼각형의 배치 규칙은 그 바로 위의 두 수의 합이다. 이는 아래와 같은 관계를 시각적으로 표현한 것이다:

 $> (\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})$

바로 위 식의 파스칼의 점화식이다. 이를 직관적으로 표현하면, n번째 원소를 포함하는 경우의 수 $(\binom{n}{k - 1})$ ^[2]와 n번째 원소를 포함하지 않는 경우의 수 $(\binom{n}{k - 1})$ ^[3]를 합치면 n개의 원소 중에서 k개를 선택하는 경우의 수가 된다는 것이다. 이 방식의 장점은 팩토리얼 계산이 필요 없으며, 단순 덧셈 연산으로 해결 가능하므로 동적 프로그래밍 적용에 매우 적합하다는 것이다.

이를 활용하여, 이항 관계에 대한 기저 조건(base case)을 분석하면 아래와 같다:

$(\binom{n}{0}) = 1$ : 아무 것도 고르지 않는 경우는 항상 1가지 (공집합)
$(\binom{n}{n}) = 1$ : 모든 원소를 고르는 경우도 항상 1가지 (전체 집합)

즉, 이항 계수에 대한 점화식은 아래와 같이 구해진다:

 $(\binom{n}{k}) = {\begin{cases} 1, & i f k = 0 o r k = n \\ (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k}), & o t h e r w i s e \end{cases}$