동적 계획법에 대해서, 이항 계수 문제

※ 웹 환경에 최적화된 서식이므로 웹 페이지로 열람함을 권장.

 

동적 계획법

기본적으로 문제를 작은 문제로 나누어 계산한 것으로 원래 문제의 답을 계산한다. (분할 정복과 같은 접근 방식) 이 과정에서 어떤 부분 문제는 두 개 이상의 더 큰 문제를 푸는데 사용된다. 즉, 같은 계산이 여러번 반복된다. 

 

계산의 중복 횟수는 분할의 깊이가 깊을수록 지수적으로 증가하므로 (Combinational Explosion) 알고리즘의 속도 개선을 위해 꼭 해결해야 한다.

 

동적 계획법에선는 각 부분 문제의 계산 결과를 저장한 뒤 필요할 때 사용하여 중복 계산을 막는다. 이를 Memoization 이라 하는데, Memoization 은 입력이 고정될 때 결과가 항상 같은 함수에만 적용 가능하다. (참조적 투명 함수, 함수의 반환 값이 그 입력 값만으로 결정되는 함수)

이항 계수

이항 계수는 이항식을 이항 정리로 전개했을 때 각 항의 계수이고 n 개의 원소 중 순서를 고려하지 않고 r 개를 뽑는 조합의 가짓수와 같다.

 

조합과 달리 순열은 n 개 중 순서를 고려하며 r 개를 뽑는 경우의 수 이다. 즉, 뽑은 것이 같아도 순서가 다르면 다른 경우로 본다. 5 개 중 3 개를 순열로 고른다고 하면 5 x 4 x 3 가지의 경우가 있다.

 

조합은 순서가 달라도 같은 경우이므로 n 개 중 r 개를 뽑는다면 r 개로 배치를 다르게 할 수 있는 경우의 수를 나눠주어 순서가 다른 경우의 수를 상쇄한다. 5 개 중 3 개를 조합으로 고르면 순열과 같이 5 x 4 x 3 가지의 경우에서 3 개의 원소로 배치를 다르게 할 수 있는 경우 3 x 2 x 1 가지를 나누면 된다. 수식으로 나타내면 n! / (n - r)! x 1 / r! 이 된다.

이항계수의 점화식

이항 계수를 구하기 위해 위의 식을 코드로 작성하면 팩토리얼 연산이 과부하를 일으킨다. 대신, 점화식으로 나타내면 연산이 쉽다.

 

1 2 3... n 이 적힌 공을 순서없이 r 개 고른다고 할 때, 만약 1 이 적힌 공을 선택했다고 하면 다음번에는 (n - 1) 개 중에서 (r - 1) 개를 골라야 한다. 1 이 적힌 공을 선택하지 않는다고 하면 다음번에는 (n - 1) 개 중에서 r 개를 골라야 한다.

 

두 경우를 모두 합하면 n 개 중 r 개를 고르는 것이므로 nCr = (n - 1)C(r - 1) + (n - 1)Cr 이 된다. (nCr 은 n 개 원소 중 순서없이 r 개를 고르는 가짓수) 이를 계수들로 나타내면 (n, r) = (n - 1, r - 1) + (n - 1, r) 이므로 곧바로 코드에 적용해보자.

Memoization 으로 중복 계산 해결하기

(n, r) = (n - 1, r - 1) + (n - 1, r) 을 코드에 적용할 때, 부분 문제가 중복 계산되는 경우를 확인해 보자. n = 5, r = 3 이라면 이를 계산하는 과정은 다음과 같다.

 

5C3 = 4C2 + 4C3

4C2 = 3C1 + 3C2,  4C3 = 3C2 + 3C3

...

 

5C3 을 계산하기 위해 4C2 를 계산할 때 3C2 를 계산하는데, 4C3 을 계산할 때 3C2 를 또 계산한다. 이런 중복은 깊은 분할로 갈수록 자주 반복된다.

 

중복된 계산을 피하기 위해 전역 변수로 저장 공간을 선언하고 부분 문제를 계산하기 위한 입력(여기서는 n 과 r)을 인덱스로 하는 배열의 위치에 계산하면서 결과를 저장한다. 부분 문제를 계산할 때 입력된 인덱스에 저장된 정보가 있다면 이미 계산한 것이므로 계산 과정을 거치지 않고 해당 위치의 정보를 반환한다.

 

아래 코드에서 함수의 입력으로 받은 인덱스 위치 [n][r] 에 대해 참조 변수를 선언하는데, 오타로 인한 잘못된 접근을 막고 배열 접근 코드를 반복하지 않아도 되므로 메모이제이션에서 자주 사용되는 방법이다.

시간 복잡도

수행 시간의 상한에 대한 간단한 계산 방법은 (존재하는 부분 문제의 수) x (한 부분 문제를 풀 때 필요한 반복문의 수행 횟수) 이다.

 

아래 코드에서 r 의 최대치는 n 이므로 bino2(n, r) 의 부분 문제 수는 최대 O(n^2) 이고, 각 부분 문제는 반복문이 없으므로 O(1) 에 해결된다. 따라서 bin2(n, r) 의 시간 복잡도는 O(n^2) 이다.

C++ 코드

#include <iostream>
using namespace std;

int bino1(int n, int r) {
	// 고를 것이 없거나(r == 0), 남은 모든 원소를 골라야 한다면(n == r)
    // 고르는 경우가 딱 한 가지 이므로 1 을 반환한다.
    if (r == 0 || n == r) return 1;

    return bino1(n - 1, r - 1) + bino1(n - 1, r);
}

// Memoization, -1 로 초기화해야 한다.
// 입력 n, r 은 최대 100.
int cache[100][100];
int bino2(int n, int r) {
    if (r == 0 || n == r) return 1;

	// 입력된 위치에 대해 참조 변수를 선언한다.
    int& ret = cache[n][r];

	// 이미 계산됐다면(-1 이 아니면) 그 값을 즉시 반환한다.
    if (ret != -1) return ret;
    return ret = bino2(n - 1, r - 1) + bino2(n - 1, r);
}