개요 :
이항 계수(Binomial Coefficient)란, 주어진 자연수 $n$과 $k$에 대해 “$n$개 중에서 $k$개를 고르는 방법의 수”를 나타내는 값이다. 이는 보통 조합(Combination)으로 불리며, 수학적으로 다음과 같이 정의된다.
$
C(n, k) = \frac{n!}{k!(n-k)!}
$
- $C(n, k)$는 $n$개 중에서 $k$개를 선택하는 경우의 수.
- $n!$은 $n$의 팩토리얼로, $n \times (n-1) \times \cdots \times 1$을 의미.
원리 :
이항 계수를 풀기 위해서는 점화식을 이용하여 재귀 호출을 해야한다.
점화식을 이용한 재귀 방식:
$$
C(n, k) =
\begin{cases}
1 & \text{if } k = 0 \text{ or } k = n \\
C(n-1, k-1) + C(n-1, k) & \text{otherwise}
\end{cases}
$$
점화식을 이용할 경우 중복 계산이 많아 큰 값에 대해 비효율적일 수 있다.
그래서 아래의 방법을 사용하게 된다.
동적 계획법:
이전에 계산한 값을 저장하여 중복 계산을 방지하므로 시간 복잡도가 O(n * k)로 최적화됩니다.
- 문제를 하위 문제로 분할
- 하위 문제들의 해결 결과를 배열에 저장
- 이를 반복하여 동일한 문제를 여러번 계산하는 비효율성을 방지
사용 조건 :
- $ n $과 $ k $는 자연수여야 합니다.
- $ k $는 $ n $보다 작거나 같아야 합니다.
- $n $과 $ k $가 커질 경우, 팩토리얼 계산에 필요한 값들이 매우 커질 수 있으므로 계산 효율성을 고려한 알고리즘을 선택하는 것이 중요합니다.
C++ 코드 예시 :
점화식
#include <iostream>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
long long result = 1;
if (k > n)
result = 0;
else if (k == 0 || k == n)
result = 1;
else
{
k = (k > n - k) ? n - k : k;
for (int i = 1; i <= k; ++i)
{
result = result * n / i;
--n;
}
}
cout << result << endl;
return 0;
}동적 계획법
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
vector<vector> dp(n + 1, vector(k + 1, 0));
for (int i = 0; i <= n; ++i)
{
dp\[i\]\[0\] = 1; // C(i, 0) = 1
dp\[i\]\[i\] = 1; // C(i, i) = 1
}
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j < i && j <= k; ++j)
{
dp\[i\]\[j\] = dp\[i - 1\]\[j - 1\] + dp\[i - 1\]\[j\];
}
}
cout << dp\[n\]\[k\] << endl;
return 0;
}문제 풀어보기 : BeakJoon