[알고리즘] 이항계수, Binomial Coefficient | 설계 및 분석

  이항계수라하면 고등학교 때 잠깐 나타나고 말 것인줄 알았거늘..... 여기서 또 마주치다니

우리에게 너무나도 익숙한 이 이항계수 _nC_k 어쩌구 저쩌구가 동적 계획법과 어떤 관련이 있다는건지 알아보자..^^

 

이항계수란?

  이항계수는 n개의 원소중에서 k개를 순서에 상관없이 뽑았을 때 조합의 가짓수이다.

파스칼의 삼각형을 이용한 이항계수의 성질은 다음과 같다.

 

_nC_k = _n-1C_k-1 + _n-1C_k

 

파스칼의 삼각형

  위 식과 그림을 보면 알 수 있듯, 파스칼 삼각형에서 n-1번째 줄 k-1번째 수와 n-1번째 줄 k번째 수를 합한 값이 n번째 줄 k번째 수의 값이 된다. 즉, 이전 항들의 수의 합이 다음 항의 수가 된다. 이는 전체 문제의 부분들이 서로 상관관계가 있다는 것이고, 따라서 이항계수는 dynamic programming으로 풀 수 있다.   

 

알고리즘 설계전략

① 재귀 관계식 정립

배열 B[i][j]에 _iC_j의 값을 넣고, 이를 재귀관계식으로 나타내면 다음과 같다.

출처: foundations of algorithms, 도경구역

 

② bottom-up 방식으로 해결

  dynamic programming은 아래서부터 부분 값을 계산하고, 이 부분 값을 사용하여 다른 부분값들을 구한다. 다시말하면 계산된 값들은 배열에 저장하고, 다시 필요할 때 이를 꺼내쓰는 방식이다. 우리는 _nC₀ , _kC_k의 값이 1이라는 것을 알고있으므로 아래 그림처럼 k=0일 때 부터 시작하여 아래에서부터 배열을 채워나간다.

 

출처: foundations of algorithms, 도경구역

 

알고리즘 수도코드

int bin(int n, int k) {
  index i, j;
  int B[0..n][0..k];
  for (i=0; i <= n; i++)
    for(j=0; j <= minimum(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];// ~ 점화식 부분 해당
  return B[n][k];
}

  위 코드에서 j에 대한 for문 내에 있는 부분은 위에서 정립한 재귀 관계식 내용이 담긴 부분이다. 

 

알고리즘 성능 분석

basic operation : 위 코드 점화식 부분 ( j에 대한 for문 )

i 값	j 루프 수행 횟수
i = 0	1
i = 1	2
. . .	. . .
i = k	k + 1
i = k + 1	k + 1
. . .	. . .
i = n	k + 1

1 + 2 + 3 + ... + k + (k+1) + ... + (k+1) = (2n - k + 2)(k+1) / 2 ∈ Θ(nk) 

∴Θ(nk) 

 

  어젠 1월 1일이었다. 올 한 해 새로운 출발을 잘 해보고싶은 마음에 글을 썼으나 막판에 급격히 찾아온 귀차니즘으로... 업로드는 하루가 지나서야 했다는.. 

저녁엔 뭘 했느냐면.. 우연히 1월 1일과 겹친 엄마 생일파티 + 동아리 사람들과 어몽어스ㅎ 올만에 해서 재밌었음

 

  다음시간엔 Floyd 알고리즘을 알아볼것이다. 구현 코드까지 올릴 예정인데 과제의 늪에 빠진 알고리즘 수업 수강생들이 복붙하기 좋을 것 같다. 문제는 내 글이 ... 검색엔진에 검색해도 안뜬다는 것 ㅋㅋㅋ