[Algorithm] 재귀함수(Recursion) 혹은 동적계획법(Dynamic Programming)을 통해 조합(Combination) 계산하기

재귀함수 혹은 동적계획법을 통해서 조합을 계산해보자


환경 및 선수조건

  • C언어 및 gcc
  • 조합에 대한 이해
  • 재귀함수와 동적계획법에 대한 이해


조합이란

조합이란 n개의 원소에서 r개를 골라내는 방법을 의미합니다. 순열은 그 수를 뽑아서 나열하는 반면 조합은 r개만 골라내면 됩니다.

Combination


조합의 구현 방법

아래의 식을 이용해 재귀함수와 동적계획법을 통해서 구현을 합니다.

식: nCr = (n-1)C(r-1) + (n-1)C(r)

Equation


재귀를 통한 조합의 구현

  • 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));

}


참고자료