[개념] 이항계수(메모이제이션) / c & c++ / 제한시간 없음

▣ 문제

이항계수는 N개의 원소를 가지는 집합에서 R개의 원소를 뽑아 부분집합을 만드는 경우의 수 를 의미한다. 공식은 nCr 로 표현된다. N과 R이 주어지면 이항계수를 구하는 프로그램을 작성하세요.

 

▣ 입력설명

- 첫 번째 줄에 자연수 N(1<=N<=20)과 R(0<=R<=20)이 주어진다. 단 (N>=R)

 

▣ 출력설명

- 첫 번째 줄에 이항계수 값을 출력한다.

 

▣ 입력 예제

5 3

 

▣ 출력 예제

10

 

<코드> - c++

#pragma warning(disable:4996)
#include<stdio.h>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int dy[21][21];

int dfs(int n, int r) {
	if (dy[n][r] > 0) return dy[n][r];
	if (n == r || r == 0) return 1;
	else return dy[n][r] = dfs(n - 1, r) + dfs(n - 1, r - 1);
}

int main() {
	int n, r;
	scanf("%d %d", &n, &r);
	printf("%d\n", dfs(n, r));
	return 0;
}

이 코드의 핵심은 dy[21][21] 이라는 변수이다.

 

이항계수는 동적계획법(Dynamic Programming)의 흔한 예시로 쓰인다. 동적계획법이란 쉽게 말하면 이전에 구한 데이터를 다시 쓰는것이다. 이를 통해서 효율적으로 계산을 할 수 있다.

 

이항계수의 성질은 nCr = n-1Cr + n-1Cr-1 이다. 이는 DFS를 통해서 쉽게 구할수 있다. 이를 코드로 그대로 사용하면

#pragma warning(disable:4996)
#include<stdio.h>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

int dfs(int n, int r) {
	if (n == r || r == 0) return 1;
	else return dfs(n - 1, r) + dfs(n - 1, r - 1);
}

int main() {
	int n, r;
	scanf("%d %d", &n, &r);
	printf("%d\n", dfs(n, r));
	return 0;
}

와 같이 될것이다.

 

하지만 결국 1C0 또는 1C1이 되야지 DFS가 끝나게 되는데 이러면 중복되는 계산을 계속 실행하기 때문에 시간적으로 비효율적이게된다. 그렇기 때문에 dy[21][21]이라는 변수를 설정해주면서 메모리 공간을 조금 더 차지하는 대신에 시간적 효율을 향상시켜준다. 이를 메모이제이션(Memoization)이라고 한다.