Binomial Coefficient [이항계수]

이항계수 알고리즘은 누구나 한 번쯤 들어봤을 법한 파스칼의 삼각형, 조합을 구하는 알고리즘입니다.

고등학교 수학에서 nCk라 표현하던 식은 2*1 행렬로 표현할 수 있습니다. 위의 식을 참고해서 분할정복으로 풀어보면,

int binomial(int n, int k){
    if(k==0 || k==n) return 1;
    return binomial(n-1,k-1)+binomial(n-1,k);
}

다음과 같은 간단한 코드가 나옵니다.. 본래 DP로 접근해야 할 문제인데, 분할정복으로 접근했을 때 얼마나 비효율적인지 구해봅시다.

무려 시간복잡도가 n! 가 나옵니다. 가장 높은 수준이라고 할 수 있지요.

이제 DP로 접근해볼건데, 분할정복과 아이디어는 같습니다.

int binomial(int n, int k){
    int dp[N][N]={};
    for(int i=0; i<=n; i++){
        for(int j=0; j<=min(i,k); j++){
            if(j==0 || j==i) dp[i][j]=1;
            else dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
        }
    }
    return dp[n][k];
}

파스칼의 삼각형을 생각하면 쉬울 듯 합니다.

파스칼의 삼각형이 좌측으로 치우친 모양인데, 항상 각 행의 첫번째 값과 마지막 값은 1입니다.

그리고 위에서 제시한 아이디어로, 그 외의 값은 (i-1,j-1)값과 (i-1,j)값을 합친 값입니다.

실행 시간을 단축시키기 위해 j는 i나 k중 더 작은 값까지 가게 되는데, 반환값은 (n,k)값이고, (n,k)값을 구하는데에 있어서 모든 j에 대해 (*,j>k)값은 필요가 없기 때문입니다.

 

DP로 접근했을 때의 시간복잡도를 구하고 마치겠습니다.