Lecture 14 - Dynamic Programming

---

동적 프로그래밍(Dynamic Programming)

동적 프로그래밍이란 큰 문제의 해답에 더 작은 문제의 해답이 포함되어 있으며, 이를 재귀호출로 구현할 때 같은 해답을 구하기 위한 중복 호출이 다수 발생하는 경우에 활용하는 문제해결 기법이다. 큰 문제의 해답에 더 작은 문제의 해답이 포함된 경우를 최적 부분 구조(Optimal Substructure)를 가진다고 한다.

 

동적 프로그래밍을 적용하는 문제는 아래와 같은 두 성질이 있다.

① 최적 부분구조(optimal substructure) - 큰 문제의 최적 솔루션에 작은 문제의 최적 솔루션이 포함된다. (점화식 형태로 표현)

② 재귀호출시 중복(overlapping recursive calls) - 재귀적 해법으로 풀면 같은 문제에 대한 재귀호출이 심하게 중복됨

 

피보나치 수열을 예시로보면 재귀호출을 이용하면 다음과 같이 fib(7)만 호출하여도 같은 내용이 굉장히 많이 중복되어 후출된다.

이런 내용을 DP를 이용한 pseudo code를 보면 다음과 같다.

fibonacci(n)
{
	f[1] ← f[2] ← 1;
	for i ← 3 to n
		f[i] ← f[i-1] +f[i-2];
	return f[n];
}

이와 같은 성질을 이해하고 다양한 예시를 살펴보자.

---

행렬 경로 문제

양수 원소들로 구성된 n×n 행렬이 주어지고, 행렬의 좌상단에서 시작하여 우하단까지 이동하는 상황을 가정한 문제이다.

이동 방법 즉,제약조건은 다음과 같다. 1. 오른쪽이나 아래쪽으로만 이동할 수 있다 2. 왼쪽, 위쪽, 대각선 이동은 허용하지 않는다.

목표는 행렬의 좌상단에서 시작하여 우하단까지 이동하되, 방문한 칸에 있는 수들을 더한 값이 최대화되도록 하여 그 최대값을 출력하는 것이다.

변수 𝑐𝑖𝑗를 (1, 1)에서 (i, j)에서 이르는 최고 점수라고 정의한다면 아래와 같은 재귀적 관계가 성립한다.

matrixPath(i, j)
▷ (i, j)에 이르는 최고점수
{
	if (i = 0 or j = 0) then return 0;
	else return (mij + (max(matrixPath(i-1, j), matrixPath(i, j-1))));
}

재귀호출을 이용할 경우의 문제는 다음과 같이 중복 호출이 너무 많다는 점이다.

따라서 다음과 같은 방법으로 DP알고리즘을 이용할 수 있다.

Θ(𝑛^2)의 시간 복잡도를 가지며, 행렬의 총 원소 수에 대해서 선형 시간으로 볼 수 있다.

matrixPath(n)
▷ (n, n)에 이르는 최고점수
{
	for i ← 0 to n
		c[i, 0] ← 0;
	for j ← 1 to n
		c[0, j] ← 0;
	for i ← 1 to n
		for j ← 1 to n
			c[i, j] ← mij + max(c[i-1, j], c[i, j-1]);
	return c[n, n];
}

---

돌 놓기 문제

3 × 𝑛 행렬의 각 칸에 양 또는 음의 정수가 기록되어 있으며, 해당 행렬에 돌을 놓는 상황이다.

돌을 놓을 때의 제약조건은 다음과 같다. 1. 가로나 세로로 인접한 두 칸에 동시에 조약돌을 놓을 수 없다. 2. 각 열에는 적어도 하나 이상의 조약돌을 놓는다. 목표는 돌이 놓인 자리에 있는 수들의 합이 최대가 되도록 돌을 놓는 것이다.

 

임의의 열을 채울 수 있는 패턴은 아래와 같이 4가지가 존재한다.

패턴별로 서로 인접한 열에서 양립할 수 있는 패턴들을 정리해보면 아래와 같다.

최적 부분구조 확인

• 𝑖열이 패턴 1일 때의 최고점: 𝑖 − 1열이 패턴 2인 경우 중 최고점 및 패턴 3인 경우 중 최고점 중 점수가 더 큰 경우에 대해서 𝑖열에서의 점수를 더한다.
• 𝑖열이 패턴 2일 때의 최고점: 𝑖 − 1열이 패턴 1인 경우 중 최고점, 패턴 3인 경우 중 최고점 및 패턴 4인 경우 중 최고점 중 점수가 더 큰 경우에 대해서 𝑖열에서의 점수를 더한다.
• 𝑖열이 패턴 3일 때의 최고점: 𝑖 − 1열이 패턴 1인 경우 중 최고점 및 패턴 2인 경우 중 최고점 중 점수가 더 큰 경우에 대해서 𝑖열에서의 점수를 더한다.
• 𝑖열이 패턴 4일 때의 최고점: 𝑖 − 1열이 패턴 2인 경우 중 최고점에 대해서 𝑖열에서의 점수를 더한다.

재귀 알고리즘을 이용하면 다음과 같다.

pebble(i, p)
▷ i 열이 패턴 p로 놓일 때의 i 열까지의 최대 점수 합 구하기
▷ w[i, p] : i 열이 패턴 p로 놓일 때 i 열에 돌이 놓인 곳의 점수 합. p {1, 2, 3, 4}
{
	if (i = 1)
		then return w[1, p] ;
	else {
		max ← -∞ ;
		for q ← 1 to 4 {
			if (패턴 q가 패턴 p와 양립)
			then {
				tmp ← pebble(i―1, q) ;
				if (tmp > max) then max ← tmp ;
			}
		}
		return (max + w[i, p]) ;
	}
}

pebbleSum(n)
▷ n 열까지 조약돌을 놓은 방법 중 최대 점수 합 구하기
{
	return max { pebble(n, p) } ;
}
✓ pebble(i, 1), …, pebble(i, 4) 중 최대값이 최종적인 답

여전히 중복 호출 문제는 많이 발생한다.

DP알고리즘을 이용하면 다음과 같이 psuedo code를 작성할 수 있다.

pebble (n)
{
	for p←1 to 4
		peb[1,p] ← w[1,p];
		for i←2 to n
			for p←1 to 4 
				peb[i, p] ← max {peb[i-1,q]} + w[i,p]; #p와 양립하는 패턴 q
	return max {peb[n, p]}; #p=1,2,3,4
}

---