[Algorithm] 재귀함수(Recursion) 혹은 동적계획법(Dynamic Programming)을 통해 조합(Combination) 계산하기
재귀함수 혹은 동적계획법을 통해서 조합을 계산해보자
환경 및 선수조건
- C언어 및 gcc
- 조합에 대한 이해
- 재귀함수와 동적계획법에 대한 이해
조합이란
조합이란 n개의 원소에서 r개를 골라내는 방법을 의미합니다. 순열은 그 수를 뽑아서 나열하는 반면 조합은 r개만 골라내면 됩니다.
조합의 구현 방법
아래의 식을 이용해 재귀함수와 동적계획법을 통해서 구현을 합니다.
식: nCr = (n-1)C(r-1) + (n-1)C(r)
재귀를 통한 조합의 구현
- Time Complexity: O(r)
combination_example.cpp
#include <stdio.h>
int combination(int n, int r){
if(n==r || r==0){
return 1;
}
// nCr = (n-1)C(r-1) + (n-1)C(r)
return combination(n-1,r-1) + combination(n-1, r);
}
int main(){
printf("%d", combination(7,4));
}
동적계획법을 통한 조합의 구현
- Time Complexity: O(n*r)
combination_example.cpp
#include <stdio.h>
#define MAX_SIZE 1000
int combination(int n, int r){
int arr[1000][1000];
// nCr = (n-1)C(r-1) + (n-1)C(r)
for(int i=0;i<=n;i++){
for(int j=0; j<=r;j++){
if(i==j || j==0)
arr[i][j] = 1;
else
arr[i][j] = arr[i-1][j-1] + arr[i-1][j];
}
}
return arr[n][r];
}
int main(){
printf("%d", combination(7,4));
}