4-(1) Dynamic Programming 1)Rod Cutting

이 챕터에서는 Dynamic Programming이라는 문제 해결 방법에 대해 배운다. 

Dynamic Programming은 어떤 문제를 해결할 때 sub문제들의 subsub문제가 overlap되는 경우 사용하는 Algorithm기법을 말한다. 책에서는 이 예시로 Rod Cutting문제를 말하고 있는데 Rod Cutting문제란 다음과 같은 문제를 말한다.

 

Q: 어떤 Value를 지닌 통나무(Rod)를 판다고 해보자. 그런데 이 통나무는 길이에 따라 매기는 값이 비례하지 않게 달라진다. 예를 들어 다음 표와 같이 길이에 따른 값이 달라진다.

<그림1: 길이에 따른 값이 담겨있는 배열 P>

이 때 주어진 길이 n의 통나무와 값이 담겨있는 배열 p에 대해 이 Rod의 max Price는?

Input: 통나무의 길이n, 값이 담긴 배열 p[1:n]

Output: 길이에 따른 Max Price가 담긴 배열 r[1:n]

 

일단, 가장 Naive하게 생각해보자. 길이 10인 통나무가 있다고 해보면 이 통나무를 자를 수 있는 방법은 총 몇개일까? 고등학교 확률과 통계 자연수의 분할을 생각해보면 10을 1개로, 2개로, 3개로, ..., 10개로 분할하는 모든 경우의 수의 합이겠지만, 가장 Naive하게 생각해보면 2⁹가지가 될 것이다. 왜냐하면 1이 10개 붙어있으면 총 9개의 자를 수 있는 틈이 있기 때문에 각 9개의 지점에서 자를 지 말지 결정하면 되기 때문이다.(가장 Naive한 생각이다. 자연수의 분할을 적용하면 이것보다 가지수가 더 적게 나올 것이다. 왜냐하면 중복되는 경우가 많이 나오기 때문. 이건 뒤에서 다루자) 그럼 이 Naive한 구현은 어떻게 가능하겠는가? 우선 길이가 n인 rod를 봤을 때 최댓값은 다음 중 하나일 것이다. r_n=max(p_n,r_i+r_n-i)(i is in [1:n-1])

즉, max Price는 그냥 안 잘랐을 때나, 어딘가 최소한 하나를 자른 경우 두 토막의 최댓값을 합한 값일 것이다. 

이 코드는 다음과 같이 구현할 수 있다. 

int rodcuttingNaive(int n, int* price,int* r) {
	if (n <1) { return 0; }
	int temp = price[n];
	for (int i = 1; i < n; i++) {
		if (temp < rodcuttingNaive(i, price, r) + rodcuttingNaive(n - i, price, r)) 
			temp = rodcuttingNaive(i, price, r) + rodcuttingNaive(n - i, price, r);
	}
	r[n] = temp;
	return temp;
}

(solution은 r에 담는다.)

이렇게 연산하게 되면 O(n)=3ⁿ의 복잡도를 갖게 된다.(복잡도 분석은 생략)

근데, 이런 연산을 조금 줄일 수 있는데, 자연수의 분할 성질을 생각해보는 것이다. 만약, 하나라도 자르는 곳이 있는 게 해라면, 왼쪽에는 무조건 하나의 잘리지 않은 통나무가 남게 될 것이다. 따라서

r_n=max(p_i+r_n-i)(i is in [0:n-1]),단 p₀=0

이렇게 연산하게 되면 O(n)=2ⁿ의 복잡도를 갖게 된다.

그런데 이렇게 되면 다음과 같이 연산을 하는 꼴이나 마찬가지다. 

<그림1: n=4일 때 일어나는 연산>

즉, 동일한 subproblem을 너무 여러번 풀게 된다. 따라서 Dynamic Programming은 다음과 같은 방법을 제시한다.

만약 이미 푼 문제라면 그냥 해를 제시하고 풀지 않은 문제일 때만 함수를 call해라

예를 들어, 저 위쪽의 problem tree에서 4-3으로 이어지는 subtree를 모두 풀었다면 오른쪽의 problem을 풀 때는 그냥 저장된 값을 주면 된다. 그런데 이런 Top-down방식으로 문제를 구현하면 if문이 하나 필요해지니까 그렇게 하지말고 그냥 Bottom-UP으로 구현하면 더 간단하게 된다. 이 Bottom-UP방식의 코드와 TestCode까지 전부 밑에 제시한다.

#include<iostream>
using namespace std;
const int INFINITE = 100000000000;

int rodcuttingNaive(int n, int* price,int* r) {
	if (n <1) { return 0; }
	int temp = price[n];
	for (int i = 1; i < n; i++) {
		if (temp < rodcuttingNaive(i, price, r) + rodcuttingNaive(n - i, price, r)) 
			temp = rodcuttingNaive(i, price, r) + rodcuttingNaive(n - i, price, r);
	}
	r[n] = temp;
	return temp;
}

int* BottomUpFashion(int n, int* price) { 
	int* r = new int[n + 1];
	r[0] = 0; //too obvious
	int temp;
	for (int i = 1; i <= n; i++) {
		temp = -INFINITE;
		for (int j = 0; j <= i; j++) {
			if (temp < price[j] + r[i - j]) temp = price[j] + r[i - j];
		}
		r[i] = temp;
	}
	return r;
}

int main() {
	int p[] = {0, 1,5,8,9,10,17,17,20,24,30 };
	int* r = new int[11];
	//(1) Test Naive Solution
	rodcuttingNaive(10, p, r);
	for (int i = 1; i < 11; i++) {
		cout << "r[" << i << "]: " << r[i] << endl;
	}
	//(2) Test Bottom Up Fashion
	int* k = BottomUpFashion(10, p);
	for (int i = 1; i < 11; i++) {
		cout << "k[" << i << "]: " << k[i] << endl;
	}
	delete k;
}

 이렇게 하면 최대 n번까지 돌아가는 for문이 2개니까 n²까지 수행시간이 줄어들게 된다. 

 

즉 Dynamic Programming의 일반적인 방법론이 무엇인지는 다음과 같이 말해볼 수 있을 것 같다.

(1) Optimal Solution의 구조를 Characterize

(2) Optimal Solution의 value를 recursively define

(3) bottom-up fashion을 통해 optimal solution의 값을 계산