이항 계수 내 맘대로 정리(with 재귀)

0. 이항계수란?  binomial coefficient?

주어진 크기의 (순서 없는) 조합의 가짓수. n개의 원소를 가지는 집합에서 크기가 r 인 부분집합을 고르는 경우의 수.

 

 

보통 위의 식과 같이 계산한다.

 

1. 재귀로 보는 이항계수

이항계수는 점화식으로 구할 수도 있다. 

 

(파스칼의 삼각형을 같이 보면 수식을 이해하기 쉽다)

 

#include <stdio.h>

long long bc(int n, int c) {
	if (n == c || c == 0) return 1;
	else return bc(n - 1, c) + bc(n - 1, c - 1);
}

int main(void) {
	int n, c;
	scanf("%d %d", &n, &c);
	printf("%lld\n", bc(n, c));

}

위의 식을 재귀로 표현했다.

 

그런데 이렇게 짜면 문제점이 생기는데, 조금만 큰 수를 넣어도 계산이 확연히 느려진다는 것이다. 왜냐하면, 이 경우 중복해서 계산하는 부분이 기하급수적으로 늘어난다. 아래 호출 트리를 보자.

 

두 번 이상 계산하는 부분을 회색깔로 칠해 보았다. 그럼, 이런 중복 계산을 없애기 위해 무엇을 할 수 있을까?

 

2. 메모이제이션

결국 요점은 계산을 한 번만 하는 것이다. 그렇다면, 한 번 계산된 결과 값을 어딘가에 저장해두고, 다시 그 값을 쓴다면 어떨까? 이를 위한 기법이 메모이제이션이다.

 

아래는 메모이제이션을 이용해서 짠 이항계수 코드다.

long long memo[200][200] = { 0, };

long long bc_memo(int n, int r) {
	if (memo[n][r] > 0)return memo[n][r];

	if (n == r || r == 0) return memo[n][r] = 1;
	else return bc_memo(n - 1, r) + bc_memo(n - 1, r - 1);

}

int main(void) {
	int n, r;
	scanf("%d %d", &n, &r);
	printf("%lld\n", bc_memo(n, r));

}

와, 메모이제이션을 사용하지 않았더라면 20 C 10을 계산할 때 호출이 369511번 걸리지만, 위의 코드를 사용한다면 201번으로 획기적으로 호출 횟수를 줄일 수 있다.

 

 

 

---

reference

https://ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD_%EA%B3%84%EC%88%98

문제로 풀어보는 알고리즘(황인욱, 김용혁)