조합알고리즘의 최적화

조합알고리즘

nCr 을 구현해야 됐던 적이 있었나?

경험적으로 재귀적으로 수행했을 때도 충분히 답이 나오는 문제만 풀어서 그런지 없었다. 

1010 다리 놓기 라는 문제를 통해 

그냥 재귀탐색과 DP를 통한 메모이제이션 탐색의 엄청난 시간 차이를 경험했다. 

조합알고리즘에 대해서 간단히 설명하자면

n개 중에서 r개를 뽑는 경우의 수를 nCr 이라고 표현하고 

수학에서는 (n - r)! / r!     또는      n! / r! * (n-r)!으로 계산 해주지 않았나?

=> 6C3 => 6 * 5 * 4 / 3 * 2 * 1 이었다.

하지만 수학이 아닌 컴퓨터에서는 

이렇게 팩토리얼 개념을 적용시켜주면 자칫 메모리를 엄청나게 

쓰다가 스택 오버플로우가 날 수 있다.

n이 충분히 커지게 되면 n!은 기하급수적으로 증가하게 된다. 

그래서 식을 다음과 같이 바꾸어주게 된다. 

nCr = (n - r + 1) / r * nCr-1

nC0 = 1(r ==0일때, basecase)

그렇다면 이 것을 cache를 써서 다음과 같이 표현해주면 완벽하다.

#include <iostream>
#include <string.h>
using namespace std;
 
int testcasenum;
int n, r;
int cache[31][31];
 
int bino(int n, int r){
    if (r == 0 || r == n){
        return 1;
    }
    if (cache[n][r] != -1) 
        return cache[n][r];
    
    return cache[n][r] = bino(n - 1, r - 1) + bino(n - 1, r);
}
 
int main(){
    cin >> testcasenum;
    for (int t = 1; t <= testcasenum; t++){
        memset(cache, -1, sizeof(cache));
        cin >> r >> n;
        cout << bino(n, r) << endl;        // nCr을 구한다.
    }
    return 0;
}