9장. 동적 프로그래밍Dynamic Programming (DP)

9장. 동적 프로그래밍 Dynamic Programming (DP)

학습목표 동적 프로그래밍이 무엇인지 이해한다. 어떤 특성을 가진 문제가 동적 프로그래밍의 적용 대상인지 감지할 수 있도록 한다. 기본적인 몇 가지 문제를 동적 프로그래밍으로 해결할 수 있도록 한다.

배경 재귀적 해법 큰 문제에 닮음꼴의 작은 문제가 깃든다 잘쓰면 보약, 잘못쓰면 맹독 관계중심으로 파악함으로써 문제를 간명하게 볼 수 있다 재귀적 해법을 사용하면 심한 중복 호출이 일어나는 경우가 있다

재귀적 해법의 빛과 그림자 재귀적 해법이 바람직한 예 재귀적 해법이 치명적인 예 퀵정렬, 병합정렬 등의 정렬 알고리즘 계승(factorial) 구하기 그래프의 DFS … 재귀적 해법이 치명적인 예 피보나치수 구하기 행렬곱셈 최적순서 구하기

도입문제: 피보나치수 구하기 f(n) = f(n-1) + f(n-2) f(1) = f(2) = 1 아주 간단한 문제지만 동적 프로그래밍의 동기와 구현이 다 포함되어 있다

피보나치수를 구하는 재귀 알고리즘 fib(n) { if (n = 1 or n = 2) then return 1;                 else return (fib(n-1) +fib(n-2)); } 엄청난 중복 호출이 존재한다

피보나치 수열의 호출 트리 중복 호출의 예 fib(7) fib(6) fib(5) fib(5) fib(4) fib(4)

피보나치수를 구하는 동적 프로그래밍 알고리즘 fibonacci(n) {         f[1] ← f[2] ← 1;         for i ← 3 to n                 f[i] ← f[i-1] +f[i-2];         return f[n]; } 선형시간에 끝난다

동적 프로그래밍의 적용 요건 최적 부분구조optimal substructure 큰 문제의 최적 솔루션에 작은 문제의 최적 솔루션이 포함됨 재귀호출시 중복overlapping recursive calls 재귀적 해법으로 풀면 같은 문제에 대한 재귀호출이 심하게 중복됨 동적 프로그래밍이 그 해결책!

문제예 1: 행렬 경로 문제 양수 원소들로 구성된 n×n 행렬이 주어지고, 행렬의 좌상단에서 시작하여 우하단까지 이동한다 이동 방법 (제약조건) 오른쪽이나 아래쪽으로만 이동할 수 있다 왼쪽, 위쪽, 대각선 이동은 허용하지 않는다 목표: 행렬의 좌상단에서 시작하여 우하단까지 이동하되, 방문한 칸에 있는 수들을 더한 값이 최소화되도록 한다

불법 이동의 예 6 7 12 5 3 11 18 17 8 10 14 9 6 7 12 5 3 11 18 17 8 10 14 9 불법 이동 (상향) 불법 이동 (좌향)

유효한 이동의 예 6 7 12 5 3 11 18 17 8 10 14 9 6 7 12 5 3 11 18 17 8 10 14 9

재귀 알고리즘 matrixPath(i, j) { if (i = 0 or j = 0) then return 0;         else return (mij + (max(matrixPath(i-1, j), matrixPath(i, j-1)))); }

호출 트리의 예 mat(4,4) mat(4,3) mat (4,2) mat(3,3) mat(4,1) mat(3,2)

DP 알고리즘 matrixPath(n) { for i ← 0 to n c[i, 0] ← 0; for j ← 1 to 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]; }

문제예 2: 돌 놓기 3×N 테이블의 각 칸에 양 또는 음의 정수가 기록되어 있다 조약돌을 놓는 방법 (제약조건) 가로나 세로로 인접한 두 칸에 동시에 조약돌을 놓을 수 없다 각 열에는 적어도 하나 이상의 조약돌을 놓는다 목표: 돌이 놓인 자리에 있는 수의 합을 최대가 되도록 조약돌 놓기

테이블의 예 6 7 12 -5 5 3 11 -8 10 14 9 13 8 4 -2

합법적인 예 합법적이지 않은 예 Violation! 6 7 12 -5 5 3 11 -8 10 14 9 13 8 4 -2 6 7

가능한 패턴 패턴 1: 패턴 2: 패턴 3: 패턴 4: 6 7 12 -5 5 3 11 -8 10 14 9 13 8 4 -2 6 임의의 열을 채울 수 있는 패턴은 4가지뿐이다

서로 양립할 수 있는 패턴들 패턴 1: 패턴 2: 패턴 3: 패턴 4: 2 1 3 1 1 2 3 2 4 2 1 3 2 3 2 서로 양립할 수 있는 패턴들 패턴 1: 2 1 3 1 패턴 2: 1 2 3 2 4 2 패턴 3: 1 3 2 3 패턴 1은 패턴 2, 3과 패턴 2는 패턴 1, 3, 4와 패턴 3은 패턴 1, 2와 패턴 4는 패턴 2와 양립할 수 있다 패턴 4: 2 4

i열과 i-1열의 관계 i-1 i 6 7 12 -5 5 3 11 -8 10 14 9 13 8 4 -2 -5 … 4 i-1열이 패턴 4로 끝나거나 … 4 i-1열이 패턴 3으로 끝나거나 -5 … -5 i-1열이 패턴 1로 끝나거나

재귀 알고리즘 pebble(i, p) { if (i = 1) then return w[1, p] ; else { ▷ 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]) ;

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

호출 트리 peb(5,1) peb(4,3) peb (3,1) peb(3,2) peb(2,2) peb(2,3) peb(2,1)

DP 적용 DP의 요건 만족 최적 부분구조 재귀호출시 중복 pebble(i, .)에 pebble(i-1, .)이 포함됨 즉, 큰 문제의 최적 솔루션에 작은 문제의 최적 솔루션이 포함됨 재귀호출시 중복 재귀적 알고리즘에 중복 호출 심함

DP 알고리즘 pebble (n) { for p ← 1 to 4 peb[1, p] ← w[1, p] ; for i ← 2 to n peb[i, p] ← max {peb[i-1, q]} + w[i, p] ; return max { peb[n, p] } ; } p와 양립하는 패턴 q p =1,2,3,4 복잡도 : Θ(n)

복잡도 분석 n * 4 * 3 = Θ(n) 복잡도 : Θ(n) pebble(n) peb[1, p] ← w[1, p] ; 기껏 4 바퀴 pebble(n) { for p ← 1 to 4 peb[1, p] ← w[1, p] ; for i ← 2 to n peb[i, p] ← max {peb[i-1, q]}+w[i, p] ; return max { peb[n, p] } ; } 무시 기껏 n 바퀴 기껏 3 가지 p와 양립하는 패턴 q p =1,2,3,4 n * 4 * 3 = Θ(n) 복잡도 : Θ(n)

문제 예 3: 행렬 곱셈 순서 행렬 A, B, C 예: A:10ⅹ100, B:100ⅹ5, C:5ⅹ50 A1, A2, A3, …, An을 곱하는 최적의 순서는? 총 n-1회의 행렬 곱셈을 어떤 순서로 할 것인가?

재귀적 관계 마지막 행렬 곱셈이 수행되는 상황 n-1가지 가능성 어느 경우가 가장 매력적인가? A1(A2 … An ) (A1A2)(A3 … An) (A1A2 A3)(A4 … An) ∙ ∙ ∙ (A1 … An-2) (An-1An) (A1 … An-1)An 어느 경우가 가장 매력적인가?

min {cik + ck+1,j + pi-1pkpj} if i<j cij = cij: 행렬 Ai, …, Aj의 곱 Ai…Aj를 계산하는 최소 비용 Ak의 차원: pk-1pk 0 if i=j min {cik + ck+1,j + pi-1pkpj} if i<j cij = i ≤ k ≤ j-1 일반형: (A1 … Ak) (Ak+1 … An)

재귀적 구현 rMatrixChain(i, j) { ▷ 행렬곱 Ai…Aj를 구하는 최소 비용 구하기 { if (i = j) then return 0;    ▷ 행렬이 하나뿐인 경우의 비용은 0 min ← ∞; for k ← i to j-1 {        q ← rMatrixChain(i, k) + rMatrixChain(k+1, j) + pi-1pkpj;  if (q < min) then min ← q; } return min; 엄청난 중복 호출이 발생한다!

동적 프로그래밍 복잡도: Θ(n3) matrixChain(i, j) { for i ← 1 to n m[i, i] ← 0; ▷ 행렬이 하나뿐인 경우의 비용은 0 for r ← 1 to n-1 ▷ r: 문제 크기를 결정하는 변수, 문제의 크기 = r+1 for i ← 1 to n-r { j ← i+r; m[i, j] ← min{m[i, k] + m[k+1, j] + pi-1pkpj}; } return m[1, n]; i ≤ k ≤ j-1 복잡도: Θ(n3)

문제 예 4: 최장 공통 부분순서LCS 두 문자열에 공통적으로 들어있는 공통 부분순서 중 가장 긴 것을 찾는다 부분순서의 예 <bcdb>는 문자열 <abcbdab>의 부분순서다 공통 부분순서의 예 <bca>는 문자열 <abcbdab>와 <bdcaba>의 공통 부분순서다 최장 공통 부분순서longest common subsequence(LCS) 공통 부분순서들 중 가장 긴 것 예: <bcba>는 문자열 <abcbdab>와 <bdcaba>의 최장 공통 부분순서다

최적 부분구조 두 문자열 Xm = <x1x2 … xm>과 Yn = <y1y2 … yn>에 대해 Xm과 Yn의 LCS의 길이는 Xm-1과 Yn-1의 LCS의 길이보다 1이 크다 xm≠ yn이면 Xm과 Yn의 LCS의 길이는 Xm과 Yn-1의 LCS의 길이와 Xm-1과 Yn의 LCS의 길이 중 큰 것과 같다 0 if i = 0 or j = 0 ci-1, j-1 + 1 if i, j > 0 and xi= yj max{ci-1, j, ci, j-1} if i, j > 0 and xi ≠ yj cij = cij : 두 문자열 Xi = <x1x2 … xi>과 Yj = <y1y2 … yj>의 LCS 길이

재귀적 구현 LCS(m, n) ▷ 두 문자열 Xm과 Yn의 LCS 길이 구하기 {         if (m = 0 or n = 0) then return 0;         else if (xm= yn) then return LCS(m-1, n-1) + 1;         else return max(LCS(m-1, n), LCS(m, n-1)); } 엄청난 중복 호출이 발생한다!

호출 트리의 예 LCS(3,4) LCS(3,3) LCS(2,3) LCS(2,2) LCS(2,1) LCS(1,3)

동적 프로그래밍 복잡도: Θ(mn) LCS(m, n) ▷ 두 문자열 Xm과 Yn의 LCS 길이 구하기 {         for i ← 0 to m                 C[i, 0] ← 0;         for j ← 0 to n                 C[0, j] ← 0;         for i ← 1 to m                 for j ← 1 to n                         if (xi= yj) then C[i, j] ← C[i-1, j-1] + 1;                           else C[i, j] ← max(C[i-1, j], C[i, j-1]);         return C[m, n]; } 복잡도: Θ(mn)

문제 예 5: 최단경로 optional Weighted digraph G=(V, E) 목표 wij : vertex i에서 vertex j에 이르는 edge의 길이 Edge가 없으면 ∞ 목표 시작점 s에서 다른 각 정점vertex에 이르는 최단거리를 모두 구한다

dtk : 중간에 최대 k 개의 edge를 거쳐 s로부터 vertex t에 이르는 최단거리 목표: dtn-1 Note! For i≠s, dt0 = ∞ dt1 = ws,t 다음 페이지로 넘어가기 전에 무엇을 중심으로 관계를 파악할 지 스스로 생각해보자

재귀적 관계 dtk = min {drk-1+ wrt} ds0 = 0; dt0 = ∞; for all edges (r, t)

DP 알고리즘 a b Propagation 되는 모습이 떠오르면 잘 이해한 것! Ballman-Ford(G, s) { ds ← 0; for all vertices i ≠ s di ← ∞; for k ← 1 to n-1 { for all edges (a, b) { if (da + wab < db ) then db ← da + wab ; } b a Propagation 되는 모습이 떠오르면 잘 이해한 것!

(a) (b) i =1 (c) i =2 (e) i =4 (d) i =3 (f) i =5 8 9 10 1 3 -12 -7 11 -15 ∞ (b) i =1 8 9 10 1 3 -12 -7 11 2 4 5 -15 ∞ 8 9 10 1 3 -12 -7 11 2 4 5 -15 19 -6 ∞ (c) i =2 8 9 10 1 3 -12 -7 11 2 4 5 -15 6 (f) i =5 8 9 10 1 3 -12 -7 11 2 4 5 -15 16 12 -8 6 (e) i =4 8 9 10 1 3 -12 -7 11 2 4 5 -15 19 7 12 -6 (d) i =3

(f) i =5 (i) (g) i =6 (h) i =7 8 9 10 1 3 -12 -7 11 2 4 5 -15 6 8 9 10 6 (f) i =5 8 9 10 1 3 -12 -7 11 2 4 5 -15 -3 (g) i =6 (h) i =7 8 9 10 1 3 -12 -7 11 2 4 5 -15 7 -5 -18 6 8 9 10 1 3 -12 -7 11 2 4 5 -15 7 -5 -18 6 (i)

Thank you