8장. 동적 프로그래밍Dynamic Programming (DP) 쉽게 배우는 알고리즘 8장. 동적 프로그래밍Dynamic Programming (DP) http://academy.hanb.co.kr

8장. 동적 프로그래밍 Dynamic Programming (DP) 계시란 바깥 어딘가에서 우리한테 갑자기 주어지는 객관적 지식이 아니다. 만물의 근원에 대한 본질적인 귀속감, 우리가 거기에 아주 밀접하게 닿아 있다는 관계성을 스스로가 발견해내는 것이 계시다. -데이빗 스타인들-라스트

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

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

개 요 분할정복법(Divide & Conquer) 기법 하향식 접근법(Top-down Approach), 나누어진 부분들 사이에 서로 상관관계가 없는 문제를 해결하는데 적합 예) Binary Search, Finding The Maixmum and Minimum, Merge Sort , Quick Sort , Selection, Strassens Matrix Multiplication, Convex Hull Fibonacci 알고리즘 경우 나누어진 부분들이 서로 연관이 있다. f(5)를 계산하기 위해 f(2)를 세 번 사용? 분할정복식 방법을 적용하여 알고리즘을 설계하게 되면 같은 항을 한 번 이상 계산하는 결과를 초래하게 되므로 비효율적 Divide & Conquer 기법은 부적합

개 요 (Continued…) Dynamic Programming 기법 상향식 해결법(Bottom-up Approach)을 사용하여 알고리즘을 설계하는 방법 Divide & Conquer 기법과 마찬가지로 문제를 나눈 후에 나누어진 부분들을 먼저 푼다. 그러나 이미 풀어서 답을 알고 있는 부분의 결과가 다시 필요한 경우에는 반복하여 계산하는 대신에 이미 계산된 결과를 그냥 사용한다. Divide & Conquer는 위에서 시작하여 필요한 계산을 해 나가는 반면에, Dynamic Programming은 밑에서 시작하여 결과를 저장하면서 원하는 답을 찾아 나간다.

개 요 (Continued…) 동적 계획법(Dynamic Programming) 주어진 문제를 여러 개의 작은 문제로 분할하여 각 소문제의 해결안을 바탕으로 주어진 문제를 해결 각 작은 문제는 다시 또 여러 개의 작은 문제로 분할가능 각 작은 문제는 원래 주어진 문제와 동일한 문제이지만 입력의 크기가 작음 작은 문제의 해를 표 형식으로 저장해 놓고 이를 이용 입력 크기가 큰 원래의 문제를 점진적으로 해결 작은 문제들의 해를 먼저 구하여 저장하고 더 큰 문제의 해를 구할 때 작은 문제의 해를 반복 계산하지 않고 저장된 결과를 사용하는 것

특징 및 장단점 특징 주어진 문제의 해를 구하기 위한 순환적인 성질(Recursive Property)을 구성하여야 한다. 상향식으로 작은 부분 문제부터 해를 구하여야 한다. 장점 프로그램을 구현할 때에는 필요한 모든 가능성을 고려해서 구현하게 된다. 따라서 Dynamic Programming을 이용하여 항상 최적의 결과를 얻을 수 있다. 단점 모든 가능성에 대한 고려가 불충분할 경우 최적의 결과를 보장할 수 없다. 동적 계획법을 구현하기 위해서는 충분히 많은 가능성에 대한 고려를 해야 한다. 다른 방법론에 비해 많은 표(배열)을 이용하므로 메모리를 많이 요구한다.

재귀적 해법의 빛과 그림자 재귀적 해법이 바람직한 예 재귀적 해법이 치명적인 예 Quick Sort, Merge Sort 등의 Sort Algorithm Factorial 구하기 Graph의 DFS … 재귀적 해법이 치명적인 예 Fibonacci 수 구하기 행렬곱셈 최적순서 구하기

도입 문제: Fibonacci 수 구하기 fn = fn-1 + fn-2 f(1) = f (2) = 1 1+1+2+3+5+8+13+… 아주 간단한 문제지만 Dynamic Programming의 동기와 구현이 모두 포함

Fibonacci 수를 구하는 Recursive Algorithm fib(n) {         if (n = 1 or n = 2)                 then return 1;                 else return (fib(n-1) +fib(n-2)); } 엄청난 중복 호출이 존재한다 재귀적 알고리즘은 지수함수에 비례하는 시간이 든다.

Fibonacci 수열의 Call Tree 중복 호출의 예

Fibonacci 수를 구하는 DP Algorithm fibonacci(n) {         f[1] ← f[2] ← 1;         for i ← 3 to n                 f[i] ← f[i-1] +f[i-2]; // 배열에 저장해 주었던 값을 가져다 사용         return f[n]; } Θ(n) 시간에 끝난다

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

문제 예 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

Recursive Algorithm matrixPath(i, j) {         if (i = 1 and j = 1) then return mij;         else if (i = 1) then return (matrixPath(1, j-1) + mij); // 오른쪽 수평 이동         else if (j = 1) then return (matrixPath(i-1, 1) + mij); // 아래로 수직 이동         else return ((max(matrixPath(i-1, j), matrixPath(i, j-1)) + mij); // 원소 (i, j)의 바로 왼쪽 원소에 이르는 최고 점수와 원소(i, j)의 바로 위쪽 원소에 이른 최고 점수 중 큰 것에 원소 (i, j)의 값을 더한 것 }

Call Tree mat(4,4) mat(4,3) mat (4,2) mat(3,3) mat(4,1) mat(3,2)

Dynamic Programming Complexity: O(n2) matrixPath(i, j) { matrix[i][i] Dynamic Programming 6 7 12 -8 10 14 11 c[i][1] 6 -2 9 c[1][1] 6 matrixPath(i, j) ▷ (i, j)에 이르는 최고점수 {         c[1,1] ← m11 ;         for i ← 2 to n                 c[i,1] ← mi1 + c[i-1,1];         for j ← 2 to n                 c[1, j] ← m1j + c[1, j-1];         for i ← 2 to n                                      for j ← 2 to n    // 배열의 두 원소 중 큰 것 고르기                        c[i, j] ← mij + max(c[i-1, j], c[i, j-1]);         return c[n, n]; } c[1][i] 6 13 25 c[i][i] 6 13 25 -2 23 39 9 35 46 Complexity: O(n2)

문제 예 2: 조약돌(Pebble) 놓기 규칙 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

임의의 열에 놓을 수 있는 4가지 패턴 패턴 1: 패턴 2: 패턴 3: 패턴 4: 6 7 12 -5 5 3 11 -8 10 14 9 13 8 4 -2 패턴 1: 6 7 12 -5 5 3 11 -8 10 14 9 13 8 4 -2 패턴 2: 6 7 12 -5 5 3 11 -8 10 14 9 13 8 4 -2 패턴 3: 6 7 12 -5 5 3 11 -8 10 14 9 13 8 4 -2 패턴 4: 임의의 열을 채울 수 있는 패턴은 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-1 i 6 7 12 -5 5 3 11 -8 10 14 9 13 8 4 -2 -5 … 4 … 4 … -5 i 열과i-1열의 관계를 파악해 보자 i열 패턴4인 경우: i-1열 패턴 2로 놓여 있을 때 최고점과 i열에서 패턴 4로 놓은 곳의 합 i열 패턴1인 경우: i-1열 패턴 2로 놓여 있을 때 최고점과 i-1열 패턴 3로 놓여 있을 때 최고점 중 큰 것과 i열 패턴 1로 놓은 곳의 합 최적 부분구조: 이처럼 자신보다 크기가 하나 작은 문제의 최적 해를 자신의 최적해 구성에 사용

Recursive Algorithm pebble(i, p) { if (i = 1) then return w[1, p] ; ▷ 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 (w[i, p] + max) ;

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

Call Tree peb(5,1) peb(4,3) peb (3,1) peb(3,2) peb(2,2) peb(2,3)

Dynamic Programming 적용 DP의 요건 만족 Optimal substructure pebble(i, .)에 pebble(i-1, .)이 포함됨 즉, 큰 문제의 최적 솔루션에 작은 문제의 최적 솔루션이 포함됨 Overlapping recursive calls 재귀적 알고리즘에 중복 호출 심함

Dynamic Programming 복잡도 : O(n) pebbleSum(n) peb[1, p] ← w[1, p] ; { for p ← 1 to 4 peb[1, p] ← w[1, p] ; for i ← 2 to n { for p ← 1 to 4 { peb[i, p] ← w[i, p] + max {peb[i-1, q]} ; } return max { peb[n, p] } ; 패턴 q는 패턴 p와 양립 p =1,2,3,4 복잡도 : O(n)

Complexity n * 4 * 3 = O(n) Complexity: O(n) pebbleSum(n) 기껏 4 바퀴 pebbleSum(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] ← w[i, p] + max {peb[i-1, q]} ; } return max { peb[n, p] } ; 무시 기껏 n 바퀴 기껏 3 가지 패턴 q는 패턴 p와 양립 p =1,2,3,4 n * 4 * 3 = O(n) Complexity: O(n)

문제 예 3: Matrix-Chain Multiplication Matrices A, B, C (AB)C = A(BC) 예: A:10ⅹ100, B:100ⅹ5, C:5ⅹ50 (AB)C: 7500번의 곱셈 필요 A(BC): 75000번의 곱셈 필요 A1, A2, A3, …, An을 곱하는 최적의 순서는?

Recursive Relation 마지막으로 matrix multiplication이 수행되는 상황 n-1 가지 가능성 (A1 … An-1)An (A1 … An-2) (An-1An) ∙ ∙ ∙ (A1A2)(A3 … An) A1(A2 … An ) 어느 경우가 가장 매력적인가?

min {m[i, k] + m[k+1, j] + pi-1pkpj} , i<j m[i, j] = m[i, j]: Ai, Ai+1, …, Aj를 곱하는 최소 비용 Ak의 차원: pk-1pk 0 , i=j min {m[i, k] + m[k+1, j] + pi-1pkpj} , i<j m[i, j] = i ≤ k ≤ j-1

Recursive Algorithm rMatrixChain(i, j) { ▷ 행렬곱 을 구하는 최소 비용 구하기 { 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; 엄청난 중복 호출이 발생한다!

DP Complexity: Θ(n3) matrixChain(i, j) { for i ← 1 to n m[i, i] ← 0; ▷ 행렬이 하나뿐인 경우의 비용은 0 for r ← 1 to n-1 ▷ 문제의 크기 = 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]; ~10/10/2007 i ≤ k ≤ j-1 Complexity: Θ(n3)

문제 예 4: Longest Common Subsequence(LCS) 두 string에 공통적으로 들어있는 common subsequence들 중 가장 긴 것을 찾는다 Subsequence의 예 <bcdb>는 문자열 <abcbdab>의 subsequence이다 Common subsequence의 예 <bca>는 문자열 <abcbdab>와 <bdcaba>의 common subsequence이다 Longest common subsequence(LCS) Common subsequence들 중 가장 긴 것 예: <bcba>는 string <abcbdab>와 <bdcaba>의 LCS이다

Optimal Substructure 두 string Xm = <x1x2 … xm>과 Yn = <y1y2 … yn>에 대해 xm= 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 길이

Recursive Algorithm 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)); } 엄청난 중복 호출이 발생한다!

Call Tree LCS(3,4) LCS(3,3) LCS(2,3) LCS(2,2) LCS(2,1) LCS(1,3)

DP Complexity: Θ(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 (xm= yn) 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]; } Complexity: Θ(mn)

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

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

Recursive Relation dtk = min {drk-1+ wr, t} 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 + wa,b < db ) then db ← da + wa,b ; } 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 (i) 8 9 10 1 3 -12 -7 11 2 4 5 -15 7 -5 -18 6

Thank you