[C][순환][반복] 이항 계수 계산

이항 계수(Binomial coefficient)는 다음과 같이 표현할 수 있다.

또한 이항 계수에 대해 다음과 같은 식이 성립한다.

 (반복 알고리즘에 사용)

 (순환 알고리즘에 사용)

이항 계수를 계산하는 프로그램을 반복 알고리즘과 순환 알고리즘을 만들어보자.

먼저 반복 알고리즘을 사용하는 방법이다.

#include <stdio.h>
 
int factorial(int n) {
    int i, result = 1;
    for(i = n; n > 0; n--)
        result *= n;
    return result;
}
 
int main(void) {
    int n, k, result;
    n = 5; k = 2;
    result = factorial(n) / (factorial(k) * factorial(n-k));
    printf("%dC%d = %d\n", n, k, result);
    return 0;
}

이항 계수 정의 그대로 팩토리얼을 사용하여 프로그램을 만들어 볼 수 있다.

다만 이 방법은 비효율적으로 느껴진다.

팩토리얼은 값이 커질 수록 실행하는 연산의 수가 급격히 커지기 때문이다.

따라서 다음과 같은 프로그램도 만들어 보았다. 

#include <stdio.h>
 
int factorial(int n) {
    int i, result = 1;
    for(i = n; n > 0; n--)
        result *= n;
    return result;
}
 
int nCk(int n, int k) {
    if(k == 0 || k == n) return 1;
    else if ((0 < k) && (k < n)) {
        int i, numerator = 1;
        if(k > n/2) k = n - k;
        for(i = 1; i <= k; i++, n--)
        numerator *= n;
        return numerator / factorial(k);    
    }
    else return 0;
}
 
int main(void) {
    int n, k, result;
    n = 7; k = 5;
    result = nCk(n, k);
    printf("%dC%d = %d\n", n, k, result);
    return 0;
}

이 프로그램은 우리가 일반적으로 이항 계수를 구할 때의 방식과 동일하게 작동한다.

예를 들어 7C5를 구한다고 하자.

우리는 이항 계수의 성질을 이용하여 7C2를 구할 것이다.

또한 7C2를 구할 때에도 7! / (2! * 5!)을 계산하는 대신 7 * 6 / 2! 을 계산할 것이다.

7! = 7 * 6 * 5! 이니 굳이 일일히 팩토리얼을 계산하지 않고 약분을 하면 되기 때문이다.

따라서 위 프로그램도 팩토리얼을 최소한으로 계산하도록 하였다.

다음으로는 순환 알고리즘을 사용해보자.

이항 계수의 성질을 사용하면 쉽게 만들 수 있다.

#include <stdio.h>
 
int nCk(int n, int k) {
    if(k == 0 || k == n) return 1;
    else if ((0 < k) && (k < n)) 
        return nCk(n-1, k-1) + nCk(n-1, k);
    else return 0;
}
 
int main(void) {
    int n, k, result;
    n = 7; k = 5;
    result = nCk(n, k);
    printf("%dC%d = %d\n", n, k, result);
    return 0;
}

위 프로그램은 순환 알고리즘을 사용하였기 때문에 동일한 계산을 반복한다는 문제점을 가지고 있다.

이러한 비효율적인 방법 대신, 메모이제이션(Memoization)을 활용해 프로그램을 만들어 보자.

메모이제이션이란 한 번 그 값을 계산하였다면 값을 저장해두어, 다시 계산해야 할 때 계산하는 대신 값을 바로 가져오는 방법이다.

#include <stdio.h>
#define MAX_SIZE 100
 
int nCk(int n, int k) {
    static int arr[MAX_SIZE][MAX_SIZE];
    if(arr[n][k] > 0) return arr[n][k];
    else if(k == 0 || k == n) return arr[n][k] = 1;
    else if ((0 < k) && (k < n)) return arr[n][k] = nCk(n-1, k-1) + nCk(n-1, k);
    else return 0;
}
 
int main(void) {
    int n, k, result;
    n = 7; k = 5;
    result = nCk(n, k);
    printf("%dC%d = %d\n", n, k, result);
    return 0;
}
 

한 번 계산을 하면 배열 arr에 값을 삽입해두고 나중에 동일한 값을 계산해야 될 시 그 값을 그대로 사용한다.

이 방법을 통해 우리는 동일한 계산을 여러 번 반복하지 않아도 된다.

• 거듭제곱의 값 계산을 통해 순환 알고리즘과 반복 알고리즘 비교해보기
• 파보나치 수열의 계산을 통해 순환 알고리즘과 반복 알고리즘 비교해보기
• 순환 알고리즘을 통해 하노이탑 문제 해결해보기