C++ 이항 계수 계산하기: 재귀 호출부터 동적 프로그래밍까지

이항 계수란?

이항 계수(binomial coefficient)는 c(n,k) 또는 ⁿC_k로 표기하며, 이항식 (1+X)ⁿ을 전개했을 때 x^k 항의 계수로 정의됩니다.

또한 이항 계수는 n개의 서로 다른 대상 중에서 k개를 선택하는 경우의 수, 즉 n개 원소로 이루어진 집합의 k-조합(k-combination) 개수를 나타냅니다. 이때 선택 순서는 고려하지 않습니다.

이 글에서는 두 개의 매개변수 n과 k가 주어졌을 때, 이항 계수 ⁿC_k의 값을 구하는 방법을 알아보겠습니다.

예시

입력 : n = 8, k = 3
출력 : 56

이 문제는 여러 가지 방법으로 해결할 수 있습니다.

일반적인 해결 방법: 재귀 호출

재귀 호출(recursion)을 이용하여 c(n,k)의 값을 계산할 수 있습니다. 재귀 호출을 사용하는 이항 계수의 표준 공식은 다음과 같습니다.

c(n,k) = c(n-1, k-1) + c(n-1, k)

c(n, 0) = c(n, n) = 1

이 공식은 파스칼의 삼각형(Pascal's Triangle) 성질에 기반하며, 각 단계마다 문제를 더 작은 하위 문제로 분할하여 해결합니다.

위 공식을 활용한 재귀 함수 구현은 다음과 같습니다.

예제 코드

#include <iostream>
using namespace std;
int binomialCoefficients(int n, int k) {
   if (k == 0 || k == n)
   return 1;
   return binomialCoefficients(n - 1, k - 1) + binomialCoefficients(n - 1, k);
}
int main() {
   int n=8 , k=5;
   cout<<"C("<<n<<", "<<k<<")의 값은 "<<binomialCoefficients(n, k);
   return 0;
}

출력 결과

C(8, 5)의 값은 56

동적 프로그래밍을 이용한 최적화

재귀 방식은 동일한 하위 문제를 반복해서 계산하게 되어 비효율적일 수 있습니다. 이러한 중복되는 부분 문제(overlapping subproblems)를 해결하기 위해 동적 프로그래밍(dynamic programming) 기법을 적용할 수 있습니다.

아래 코드는 1차원 배열을 활용하여 시간 복잡도 O(n×k), 공간 복잡도 O(k)로 이항 계수를 효율적으로 계산합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
int binomialCoefficients(int n, int k) {
   int C[k+1];
   memset(C, 0, sizeof(C));
   C[0] = 1;
   for (int i = 1; i <= n; i++) {
      for (int j = min(i, k); j > 0; j--)
         C[j] = C[j] + C[j-1];
   }
   return C[k];
}
int main() {
   int n=8, k=5;
   cout<<"C("<<n<<", "<<k<<")의 값은 "<<binomialCoefficients(n,k);
   return 0;
}

출력 결과

C(8, 5)의 값은 56

마무리

재귀 방식은 구현이 간단하지만 중복 계산으로 인해 지수 시간 복잡도를 가지게 됩니다. 반면 동적 프로그래밍 방식은 O(n×k)의 시간 복잡도로 훨씬 효율적입니다. 따라서 입력 크기가 커지는 상황이라면 동적 프로그래밍 접근 방식을 사용하는 것이 바람직합니다.