[알고리즘] 재귀함수 - 이항계수(중복조합)

재귀함수 - 이항계수(중복조합)

A,B,C,D 4개의 공 중에 2개의 공을 뽑을 때 뽑을 수 있는 가지 수는 모두 몇가지일까

다음과 같은 경우의 수를 계산할때 이항계수가 사용된다.

이항계수로 경우의 수를 구하는 공식은 고등학교 과정에서 배울 수 있다.

재귀에서 이항계수를 이용하려면 다음과 같은 이항계수의 성질을 사용한다.

왜 이와 같은 성질이 나올수 있을까.

기본 nCr 식은 다음과 같이 나눌수있다.

1.  1을 포함하는 경우 : 2,3,4 중에 2개를 선택하는 경우의수(3C2)

2. 1을 포함하지 않는 경우 : 2,3,4중에 3개를 선택하는 경우의 수(3C3)

이렇게 나누어진 식이 재귀로 계산된다.

1. 중복조합을 재귀함수로

#include<stdio.h>
 
int combination(int N_num,int R_num);
 
int main() {
    int N_num, R_num, result;
 
    scanf_s("%d %d", &N_num,& R_num);
    result = combination(N_num,R_num);
 
    printf("%d\n", result);
 
    return 0;
}
 
int combination(int N_num,int R_num){
    
    if ((N_num == R_num)||R_num==0) {
        return 1;
    }
 
    return combination(N_num-1,R_num-1)+combination(N_num-1, R_num);                                           
}
 

아래의 Combination 함수를 보면 return 다음에 자신을 호출하는 재귀함수로,

점화식이 그대로 코드화 된 것을 확인할 수 있다.

또한 조건문은 1일때 최종으로 계산되는 조건을 담았다.

재귀로 계산되는 이항계수의 값은 어느 시점을 기준으로 

기하급수적으로 증가하기 때문에

long long으로 반환형을 만들어 주는게 좋다.

2. 메모이제이션(Memoization)

#include<stdio.h>
 
#define Capa 100
 
int combination(int N_num,int R_num);
 
int main() {
    int N_num, R_num, result;
 
    scanf_s("%d %d", &N_num,& R_num);
    result = combination(N_num,R_num);
 
    printf("%d\n", result);
 
    return 0;
}
 
int combination(int N_num,int R_num){
    int Buf[Capa][Capa];
 
    if (Buf[N_num][R_num]>0) {
        return Buf[N_num][R_num];
    }
 
    if ((N_num == R_num)||R_num==0) {
        return 1;
    }
 
    return Buf[N_num][R_num] =  combination(N_num-1,R_num-1)+combination(N_num-1, R_num);                   
}
 

1번 예제의 경우 별 무리 없이 잘 동작하나, 불필요한 계산이 너무 많이 수행된다.

예를 들면, 5C3의 계산에서 3C2는 3번 나왔고 다른 중복조합 또한 중복되어 등장했다.

따라서 2번 예제는, 이차원 배열에 인덱스에 해당하는 중복 조합을 저장해놓고 만약 그 인덱스에 값이 있을 경우 먼저 계산했다고 판단하여 그 값을 반환한다.

이를 메모이제이션(Memoization)이라고 하며 

재귀함수에서 불필요한 계산을 엄청나게 줄일 수 있다.