(알고리즘) 이항계수



3. 이항 계수 구하는 문제

nCr = n-1Cr-1 + n-1Cr 공식 이용하여 이항 계수 계산

분할 정복
?
1
2
3
4
5
int bincoeff(int n, int k)
{
    if(k==0 || k==n) return 1;
    else return bincoeff(n-1, k-1) + bincoeff(n-1, k);
}

동적 프로그래밍
?
1
2
3
4
5
6
7
8
9
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];

댓글

이 블로그의 인기 게시물

(네트워크)폴링방식 vs 롱 폴링방식

(ElasticSearch) 결과에서 순서 정렬

(18장) WebSocekt과 STOMP를 사용하여 메시징하기