재귀함수(3): 조합

1. 조합

순열과 조합 시간에 배운 것은 다들 기억하고 있을 것이다. 조합은 보통 다음과 같이 기억하고 있을 것이라고 생각한다.

$$_n C_k = \frac{n!}{k!(n-k)!}$$

이 방법이 조합의 수를 가장 빠르게 구해낼 수 있는 방법이다. 하지만 이번에는 조금 다른 재귀적 성질을 이용해보자.

조합에는 위 식 말고도 다른 재귀적 성질이 하나 존재한다.

$_n C_0 = 1$, $_n C_n = 1$

$_n C_k = _{n-1}C_{k-1} + _{n-1}C_k$

척 보면 감이 오겠지만, 위 둘은 base case이고 아래는 재귀적 성질이다.

2. 코드

써있는 그대로 작성하면 된다.

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

메모이제이션을 적용하지 않아 뭔가 아쉬움을 느낄 것이다.

3. 메모이제이션 적용

변수가 n, k 두 가지이므로 2차원 배열을 사용하면 쉽게 저장할 수 있다.

물론, 이 경우 n < k인 케이스가 아예 없으므로 사실 절반에 해당하는 메모리는 버려지게 되지만,

메모리 사이즈가 그리 크지는 않으므로 무시하자.

조금 더 큰 수까지 커버를 하기 위해 int를 long long으로 바꾸도록 하자.

long long c(int n, int k) {
	static long long mem[51][51] = { 0 };

	if (mem[n][k] > 0) return mem[n][k];
	if (k == 0 || n == k) return mem[n][k] = 1;
	return mem[n][k] = c(n - 1, k - 1) + c(n - 1, k);
}

시간 복잡도는 n과 k에 따라 조금 미묘한데,

일반적인 경우 $O(nk-k^2)$정도이다.