동적 계획법 (Dynamic Programming) -(1) 이항계수

분할 정복(Divide and Conquer)과 동적계획법

공통점 : 두 전략 모두 주어진 문제를 크기가 작은 여러 개의 부분 문제로 분할하여 부분문제들의 해를 구한 후, 그 해들을 결합하여 원래 문제에 대한 해를 구한다.

 

차이점 : 분할 정복 방식은 문제를 크기가 작은 부분 문제로 분할 후, 그 부분 문제를 독립적으로 해결한다. 그 후 그 해들을 결합하여 원래 문제의 해를 구한다. 또한, 답을 얻을 수 있는 최소 단위까지 내려가는 Top-down(하향식) 방법이다.

 

하지만 동적 계획법은, 부분 문제를 해결하여 그 해를 테이블에 저장한다. 그 후 다시 그 부분 문제를 풀어야 할 때 다시 풀지 않고 테이블을 저장된 결과를 사용한다.  접근법은 Down-top(상향식) 방법이다. 

따라서, 분할 정복 방식에서는 서로 공유되는 같은 부분 문제가 있다고 하더라도 독립적으로 반복적인 계산을 하지만, 동적 계획법에서는 이러한 반복적 계산을 피할 수있으므로 아주 효율적으로 문제를 풀 수 있다.

 

Greedy algorithm과 동적계획법

동적 계획법은 모든 방법을 일일이 검토하여 그 중 최적해를 찾아내는 주먹구구식 방법이다. 이러한 단점을 극복하기 위해 greedy algorithm이 등장했다. 차량 정체 구간에서 A->B로 가는 가장 빠른 경로를 찾는다고 하자. 동적계획법을 사용한다면 우리가 갈 수 있는 모든 상황과 교통 정체를 감안하여 최적의 경로를 찾아낸다. 반면 Greedy algorithm을 사용한다면 순간 순간 locally optimal한 경로를 찾아줄 것이다.

Greedy algorithm은 항상 최적의 해를 구해주지는 않지만, 최소 스패닝 트리, fractional knapsack problem 등 여러 문제에서 최적해를 구할 수 있음이 이미 입증되었다. 하지만 동적계획법을 사용하면 최적의 해가 보장된다는 장점이 있다. 

 

동적계획법 설계

1. 문제의 해를 구할 수 있는 재귀적인 성질을 설정한다.
2. 상향식 접근 방법에 의해 크기가 작은 문제를 먼저 해결한 후 크기가 큰 문제를 해결한다.
3. 크기가 큰 문제의 해결을 효율적으로 하기 위해 크기가 작은 문제의 해는 table에 저장한다. (같은 크기의 문제의 해를 다시 계산하는 과정을 피하기 위해서) 

이항 계수

n개의 물건에서 중복을 허락하지 않고 k개를 꺼내는 조합의 수가 바로 (n   k) 이다. 이를 이항 계수라고 부른다. 

이항 계수를 원래의 방법대로 구하면, n! 값과 k! 값을 계산해야 하기 때문에 n, k 값이 조금만 커지더라도 값을 구하기가 매우 어렵다. 따라서, 아래와 같이 재귀의 성질을 이용하여 값을 구한다고 하자.

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

하지만, 위에서 언급한 것과 같이 위 알고리즘은 각 재귀 호출마다 같은 부분 문제들을 풀어야 한다. = 매우 비효율적!

예를 들자면, bin(n-1,k) 값을 구하려면 bin(n-2,k-1)값과 bin(n-2, k) 값이 필요하고

bin(n-1,k-1)값을 구하려면 bin(n-2,k-2)값과 bin(n-2,k-1)값이 필요하다.

이와 같이, 각 재귀 호출은 서로 독립적으로 계산을 해야 하기 때문에 수행시간이 늘어난다! (중복 계산때문에)

이 때의 시간 복잡도는 스털링 공식에 의해 지수 시간 알고리즘이 된다. 

https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%84%B8%EB%A7%81_%EA%B7%BC%EC%82%AC

 

이제, 동적 계획법의 개념을 사용하여 효율적인 알고리즘을 만들어보도록 하자.

Bottom-up 방식을 사용하여 계산한다. 가장 기본적인 값부터 출발한다. 

 

B[i,j]=  B[i-1, j-1] + B[i-1,j]   if p<i<j

                                                                      =  1                                   if j = 0 or i

 

 

2차원 배열 B를 사용하여 재귀적으로 계산한 값을 안에다가 저장하도록 한다.

이런 식으로 한다면, B[i][j]의 값을 구하기 위해 필요한 모든 값들이 이미 배열 B에 저장되어 있기 때문에

한 번의 덧셈 연산에 의해 쉽게 계산할 수 있다.  결론적으로, B[n,k]의 값이 우리가 원하는 값인 (n   k)가 된다!

이 과정은 파스칼의 삼각형을 만들어가는 과정과 유사하다. 

int bin(int n, int k){
	int i,j;
	int B[MAX][MAX]; // 배열 B 생성한다.

	for (i=0;i<=n,i++){
		for (j=0;j<=min(i,k);j++){
			if (j==0 || j==i) B[i][j] = 1;
				else B[i][j] = B[i-1][j-1] + B[i-1][j];
	return B[n][k];
}

Ex ) 위의 알고리즘에 따라 B[4][2]를 구해보자.

(1) 행 0 

B[0][0] = 1

(2) 행 1

B[1][0] = 1, B[1][1] = 1

(3) 행 2

B[2][0] = 1, B[2][1] = B[1][0] + B[1][1] = 2, B[2][2] = 1

(4) 행 3

B[3][0] = 1, B[3][1] = B[2][0] + B[2][1] = 1 + 2 = 3, B[3][2] = B[2][1] + B[2][2] = 2 + 1 = 3

(5) 행 4

B[4][0] = 1, B[4][1] = B[3][0] + B[3][1] = 1 + 3 = 4, B[4][2] = B[3][1] + B[3][2] = 3 + 3 = 6

 

이 때, 반복문의 2중 중첩이기 때문에 O(n^2)의 시간복잡도를 가지게 된다.