[알고리즘] 동적프로그래밍 Part 1 - 이항 계수 문제 (Binomial Coefficient)

1. 문제 : 이항 계수(Binomial Coefficient) 문제를 해결하라.
  
  

   (for 0 <= k <= n)

2. 공식
  

   

 > 이항계수 nCk는 n개의 서로다른 물건들에서 k개의 물건들을 선택하는 방법들의 수이다. 
    그 수는 두가지의 경우의 합으로 나누어진다.
    ⓐ 특정 물건이 포함하고, 나머지 n-1개중 k-1개를 선택하는 방법  n-1Ck-1
    ⓑ 특정 물건이 포함되지 않고, 나무지 n-1개중 k개를 선택하는 방법  n-1Ck
    nCk = n-1Ck-1 + n-1Ck 가 성립하여 위의 공식이 생성된다.

3. 분할정복으로 해결한다면...
 int bincoeff(int n, int k){ // 단, n > 0 정수이고, k는 0보다크거나 같고 n보다 작거나 같은 정수이다.
   if ( k == 0 || k == n ) return 1;
   else return bincoeff(n-1,k-1) + bincoeff(n-1,k);
 }
 - 분석 : 매우 비효율적이다.
  > Why? 문제가 2개의 더 작은 하위 문제들로 나뉘어지나, 하위 문제들이 원래의 문제 만큼 크다.
             즉, 하위 문제가 상위 문제와 겹치는 경우가 발생한다. 균형취하기가 사용이 안됨(?)
 
4. 동적프로그래밍 해법
 - 설계 아이디어
 ⓐ 다음의 사실을 사용하라.
  A[n][k] -> A[n-1][k-1] + A[n-1][k] (단,n > 0 정수이고, k는 0보다크거나 같고 n보다 작거나 같은 정수이다.)
               -> 만약, n=k이거나 k=0이면 그 횟수는 1번이다.
 ⓑ 계산 순서는 A행렬에서의 행들을 첫번째 행부터 시작하여 순서대로 계산한다.
  ex) A[4][2] = 4C2를 계산하라.
   

       

5. 알고리즘 
 int bincoeff(int n, int k){
   int i, j;
   int B[0...n][0...n];
   for ( i = 0 ; i < n ; i++ ){
     for ( j = 0 ; j < min(i,k) ; j++ ) {
       if ( j == 0 || j == i ) B[i][j] = 1;
       else B[i][j] = B[i-1][j-1] + B[i-1][j];
     }
   } 

6. 분석
 - 덧셈 횟수 = ⊝(nk)
 - 분할 정복 해법보다 더 효율적이다.