다들 이항 계수 아시죠?
\(\binom{n}{k} = \frac{n!}{k!(n-k)!}\)입니다.
이때 n!를 계산하기 매우 힘드므로, 재귀 관계식을 이용하여 다음과 같이 정리할 수 있습니다.
\(\binom{n}{k}=\left\{\begin{matrix}
\binom{n-1}{k-1}+\binom{n-1}{k} & 0 < k < n \\
1 & k = 0 \, or \, k = n \\
\end{matrix}\right.\)
입니다.
이 방식을 통해 저희는 이항 계수를 구할 수 있습니다.
1. Divide and Conquer를 이용하여 풀기
아 참고로 cpp로 짰습니다.
int bin_recursion(int n, int k){
if ((k == 0) || (k == n)){
return 1;
}
else{
return bin_recursion(n-1, k-1) + bin_recursion(n-1, k);
}
}간단하죠?
근데 매우 비효율적입니다.
왜죠?
당연히 중복 계산 문제가 있으니 그렇죠.
n = 10, k = 3이라고 가정해봅시다.
그러면 9,2와 9,3으로 나뉘게 되고, 결국엔 8,2를 중복으로 계산하게 되죠?
결국 이 알고리즘이 계산하는 항의 개수는 \(2\binom{n}{k}-1\)이 됩니다.
즉, 앞서 말했듯이 분할 정복에서 분할할 때, 분할된 크기가 원래의 instance와 비슷하다면 비효율적일 수밖에 없습니다.
이 문제는 팩토리얼 시간 복잡도를 가지고 있습니다.
그렇다면 이제 이 문제를 DP를 이용해서 설계해봅시다.
2. DP를 이용하여 풀기
일단 재귀 관계식은 이미 세워 놓았으니, 문제의 답을 저장하는 배열을 만듭시다.
B[i][j]는 \(\binom{i}{j}\)를 저장하는 배열로 하겠습니다.
그렇다면 관계식은 이렇게 됩니다.
\(B[i][j]=\left\{\begin{matrix}
B[i-1][j-1] + B[i-1][j] & 0 < j < i \\
1 & j = 0 \, or \, j = i \\
\end{matrix}\right.\)
쉽죠?
이를 이용해서 한 번 memoization으로 풀어봅시다.
참고로 배열의 크기는 그냥 제가 임의로 정한 겁니다.
int arr[100][100] = {0,};
void bin_memoization(int i, int j){
if ((j == 0) || (j == i)){
arr[i][j] = 1;
}
else{
bin_memoization(i-1, j-1);
bin_memoization(i-1, j);
arr[i][j] = arr[i-1][j-1] + arr[i-1][j];
}
}음,,,솔직히 말씀드려서 뭔가 마음에 안 드네요. 결국 위의 분할 정복보다 더 안 좋아진 것 같습니다.
아무튼 이를 이용해서 재귀 호출을 반복문으로 바꾸는 bottom-up 방식, Tabulation으로 풀어봅시다.
int arr[100][100] = {0,};
int bin_DP(int n, int k){
for (int i = 0; i <= n; i++){
for (int j = 0; j <= min(k, i); j++){
if ((j == 0) || (j == i)){
arr[i][j] = 1;
}
else{
arr[i][j] = arr[i-1][j-1] + arr[i-1][j];
}
}
}
return arr[n][k];
}
i가 0부터 n까지 반복하고, j는 0부터 min(k, i)까지 반복합니다.
만약 5C3을 구하려고 한다면, 굳이 5C4는 구할 필요가 없으니까요.
3. 시간 복잡도
시간 복잡도는 간단하게 반복문의 횟수로 세봅시다.
i가 0부터 n까지 갈 때, 루프는 1, 2, 3 , ... , k + (k + 1) + (k + 1) + (k + 1) + (k + 1)이 됩니다.
따라서 이 문제는 nk의 시간 복잡도를 가집니다.
위의 분할 정복과 비교하면 천사죠?
근데 더 좋은건 위의 DP에서 튜닝까지 더 가능하다는 점입니다.
1개의 배열을 이용하여 문제를 풀 수도 있습니다.
왜냐면 이전의 배열은 다음 배열을 구하는데만 쓰고 더 이상은 쓸모가 없기 때문이죠.
또한, \(\binom{n}{k} = \binom{n}{n-k}\)을 이용할 수도 있습니다.
따라서 다음 글에는 튜닝된 이항 계수 찾기를 올리겠습니다.
감사합니다.
지적 환영합니다.