쉽게배우는알고리즘 8장. 동적프로그래밍 프로그래밍 Dynamic Programming (DP) http://academy.hanb.co.kr
IT COOKBOOK 8장. 동적프로그래밍 Dynamic Programming (DP) 계시란바깥어딘가에서우리한테갑자기주어지는객관적지식이아니다. 만물의근원에대한본질적인귀속감, 우리가거기에아주밀접하게닿아있다는관계성을스스로가발견해내는것이계시다. - 데이빗스타인들 - 라스트 - 2 - 한빛미디어
IT COOKBOOK 학습목표 동적프로그래밍이무엇인가를이해한다. 어떤특성을가진문제가동적프로그래밍의적용대상인지를감지할수있도록한다. 기본적인몇가지문제를동적프로그래밍으로해결할수있도록한다. - 3 - 한빛미디어
배경 재귀적해법 큰문제에닮음꼴의작은문제가깃든다 잘쓰면보약, 못쓰면맹독 관계중심으로파악함으로써문제를간명하게볼수있다 재귀적해법을사용하면심한중복호출이일어나는경우가있다 - 4 - 한빛미디어
재귀적해법의빛과그림자 재귀적해법이바람직한예 퀵정렬, 병합정렬등의정렬알고리즘 계승 (factorial) 구하기 그래프의 DFS 재귀적해법이치명적인예 피보나치수구하기 행렬곱셈최적순서구하기 - 5 - 한빛미디어
도입문제 : 피보나치수구하기 f n = f n-1 + f n-2 아주간단한문제지만 Dynamic programming 의동기와구현이다포함되어있다 - 6 - 한빛미디어
피보나치수를구하는 Recursive Algorithm fib(n) { if (n = 1 or n = 2) then return 1; else return (fib(n-1) +fib(n-2)); } ü 엄청난중복호출이존재한다 - 7 - 한빛미디어
피보나치수열의 Call Tree fib(7) fib(6) fib(5) fib(5) fib(4) fib(4) fib(4) fib(3) fib(3) fib(3) fib(3) fib(3) fib (2) fib(2) fib(2) fib (2) fib(2) fib (2) fib(2) fib(2) fib (1) fib(1) fib (1) fib (1) fib(1) 중복호출의예 - 8 - 한빛미디어
피보나치수를구하는 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) 시간에끝난다 - 9 - 한빛미디어
DP 의적용요건 Optimal substructure 큰문제의최적솔루션에작은문제의최적솔루션이포함됨 Overlapping recursive calls 재귀적해법으로풀면같은문제에대한재귀호출이심하게중복됨 DP가그해결책! - 10 - 한빛미디어
문제예 1: 조약돌놓기 3 N 테이블의각칸에양또는음의정수가기록되어있다 조약돌을놓는방법 ( 제약조건 ) 각열에는적어도하나의조약돌을놓아야한다 가로나세로로인접한두칸에동시에조약돌을놓을수없다 목표 : 돌이놓인자리에있는수의합을최대가되도록 조약돌놓기 - 11 - 한빛미디어
테이블의예 6 7 12-5 5 3 11 3-8 10 14 9 7 13 8 5 11 12 7 4 8-2 9 4-12 - 한빛미디어
합법적인예 6 7 12-5 5 3 11 3-8 10 14 9 7 13 8 5 11 12 7 4 8-2 9 4 합법적이지않은예 6 7 12-5 5 3 11 3-8 10 14 9 7 13 8 5 11 12 7 4 8-2 9 4 Violation! - 13 - 한빛미디어
가능한패턴 패턴 1: 6 7 12-5 5 3 11 3-8 10 14 9 7 13 8 5 11 12 7 4 8-2 9 4 패턴 2: 6 7 12-5 5 3 11 3-8 10 14 9 7 13 8 5 11 12 7 4 8-2 9 4 패턴 3: 6 7 12-5 5 3 11 3-8 10 14 9 7 13 8 5 11 12 7 4 8-2 9 4 임의의열을채울수있는패턴은 4 가지뿐이다 패턴 4: 6 7 12-5 5 3 11 3-8 10 14 9 7 13 8 5 11 12 7 4 8-2 9 4-14 - 한빛미디어
서로양립할수있는패턴들 패턴 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-15 - 한빛미디어
i-1 i 6 7 12-5 5 3 11 3-8 10 14 9 7 13 8 5 11 12 7 4 8-2 9 4 i 열과 i-1 열의관계를파악해보자 - 16 - 한빛미디어
pebble(i, p) Recursive Algorithm 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 (w[i, p] + max) ; } } - 17 - 한빛미디어
pebblesum(n) n 열까지조약돌을놓은방법중최대점수합구하기 { } return max { pebble(n, p) } ; p =1,2,3,4 ü pebble(i, 1),, pebble(i, 4) 중최대값이최종적인답 - 18 - 한빛미디어
peb(5,1) Call Tree peb(4,3) peb (3,1) peb(3,2) peb(2,2) peb(2,3) peb(2,1) peb(2,3) peb(2,4) peb(1,1)peb(1,3) peb(1,4) peb(1,1) peb(1,2) peb(1,2) peb(1,3) peb(1,1) peb(1,2) peb(1,2) peb(4,2) peb (3,1) peb(3,3) peb(3,4) peb(2,2) peb(2,3) peb(2,1) peb(2,2) peb(2,2) peb(1,1)peb(1,3) peb(1,4) peb(1,1) peb(1,2) peb(1,2) peb(1,3) peb(1,1) peb(1,3) peb(1,4) peb(1,1) peb(1,3) peb(1,4) - 19 - 한빛미디어
DP 적용 DP 의요건만족 Optimal substructure pebble(i,.) 에 pebble(i-1,.) 이포함됨 즉, 큰문제의최적솔루션에작은문제의최적솔루션이포함됨 Overlapping recursive calls 재귀적알고리즘에중복호출심함 - 20 - 한빛미디어
DP 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]} ; } 패턴 q는패턴 p와양립 return max { peb[n, p] } ; } p =1,2,3,4 ü 복잡도 : O(n) - 21 - 한빛미디어
Complexity pebblesum(n) { for p 1 to 4 peb[1, p] w[1, p] ; for i 2 to n { for p 1 to 4 { } 무시 기껏 4 바퀴 기껏 n 바퀴 peb[i, p] w[i, p] + max {peb[i-1, q]} ; 패턴 q는패턴 p와양립 } return max { peb[n, p] } ; p =1,2,3,4 기껏 3 가지 ücomplexity: O(n) n * 4 * 3 = O(n) - 22 - 한빛미디어
문제예 2: 행렬경로문제 양또는음의정수원소들로구성된 n n 행렬이주어지고, 행렬의좌상단에서시작하여우하단까지이동한다 이동방법 ( 제약조건 ) 오른쪽이나아래쪽으로만이동할수있다 왼쪽, 위쪽, 대각선이동은허용하지않는다 목표 : 행렬의좌상단에서시작하여우하단까지이동하되, 방문한칸에있는수들을더한값이최소화되도록한다 - 23 - 한빛미디어
불법이동의예 6 7 12 5 5 3 11 18 7 17 3 3 8 10 14 9 6 7 12 5 5 3 11 18 7 17 3 3 8 10 14 9 불법이동 ( 상향 ) 불법이동 ( 좌향 ) - 24 - 한빛미디어
유효한이동의예 6 7 12 5 5 3 11 18 7 17 3 3 8 10 14 9 6 7 12 5 5 3 11 18 7 17 3 3 8 10 14 9-25 - 한빛미디어
Recursive Algorithm matrixpath(i, j) (i, j) 에이르는최저점수 { if (i = 1 and j = 1) then return m ij ; else if (i = 1) then return (matrixpath(1, j-1) + m ij ); else if (j = 1) then return (matrixpath(i-1, 1) + m ij ); else return ((min(matrixpath(i-1, j), matrixpath(i, j-1)) + m ij ); } - 26 - 한빛미디어
mat(4,4) mat(4,3) mat (4,2) mat(3,3) mat(4,1) mat(3,2) mat(3,2) mat(2,3) mat(3,1) mat(3,1) mat(2,2) mat(3,1) mat(2,2) mat(2,2) mat(1,3) mat(2,1) mat(1,1) mat(2,1) mat(1,1) mat(2,1) mat(1,2) mat(1,1) mat(1,1) mat(2,1) mat(1,1) mat(2,1) mat(1,2) mat(1,1) mat(1,1) mat(2,1) mat(1,2) mat(1,1) mat(1,1) mat(1,2) mat(1,1) mat(3,4) mat(2,4) mat(3,3) Call Tree mat(1,4) mat(2,3) mat(2,3) mat(3,2) mat(1,3) mat(1,2) mat(1,1) mat(1,3) mat(1,2) mat(1,1) mat(2,2) mat(1,2) mat(2,1) mat(1,1) mat(1,1) mat(2,2) mat(1,3) mat(3,1) mat(2,2) mat(1,2) mat(2,1) mat(2,1) mat(1,2) mat(2,1) mat(1,2) mat(1,1) mat(1,1) mat(1,1) mat(1,1) mat(1,1) mat(1,1) - 27 - 한빛미디어
DP matrixpath(i, j) (i, j) 에이르는최저점수 { c[1,1] m 11 ; for i 2 to n c[i,1] m i1 + c[i-1,1]; for j 2 to n c[1, j] m 1j + c[1, j-1]; for i 2 to n for j 2 to n } c[i, j] m ij + min(c[i-1, j], c[i, j-1]); return c[n, n]; ücomplexity: O(n 2 ) - 28 - 한빛미디어
문제예 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번의곱셈필요 A 1, A 2, A 3,, A n 을곱하는최적의순서는? - 29 - 한빛미디어
Recursive Relation 마지막으로 matrix multiplication 이수행되는상황 n-1 가지가능성 (A 1 A n-1 )A n (A 1 A n-2 ) (A n-1 A n ) (A 1 A 2 )(A 3 A n ) A 1 (A 2 A n ) 어느경우가가장매력적인가? - 30 - 한빛미디어
ü m[i, j]: A i, A i+1,, A j 를곱하는최소비용 ü A k 의차원 : p k-1 p k m[i, j] = 0, i=j min {m[i, k] + m[k+1, j] + p i-1 p k p j }, i<j i k j-1-31 - 한빛미디어
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) + p i-1 p k p j ; if (q < min) then min q; } return min; } ü 엄청난중복호출이발생한다! - 32 - 한빛미디어
DP 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] + p i-1 p k p j }; i k j-1 } return m[1, n]; } ü Complexity: Θ(n 3 ) - 33 - 한빛미디어
문제예 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 이다 - 34 - 한빛미디어
Optimal Substructure 두 string X m = <x 1 x 2 x m > 과 Y n = <y 1 y 2 y n > 에대해 x m = y n 이면 X m 과 Y n 의 LCS 의길이는 X m-1 과 Y n-1 의 LCS 의길이보다 1 이크다 x m y n 이면 X m 과 Y n 의 LCS 의길이는 X m 과 Y n-1 의 LCS 의길이와 X m- 1 과 Y n 의 LCS 의길이중큰것과같다 c ij = 0 if i = 0 or j = 0 c i-1, j-1 + 1 max{c i-1, j, c i, j-1 } if i, j > 0 and x i = y j if i, j > 0 and x i y j ü c ij : 두문자열 X i = <x 1 x 2 x i > 과 Y j = <y 1 y 2 y j > 의 LCS 길이 - 35 - 한빛미디어
Recursive Algorithm LCS(m, n) 두문자열 X m 과 Y n 의 LCS 길이구하기 { if (m = 0 or n = 0) then return 0; else if (x m = y n ) then return LCS(m-1, n-1) + 1; else return max(lcs(m-1, n), LCS(m, n-1)); } ü 엄청난중복호출이발생한다! - 36 - 한빛미디어
LCS(3,4) LCS(3,3) LCS(2,3) LCS(3,2) LCS(1,3) LCS(2,2) LCS(3,1) LCS(2,2) LCS(0,3) LCS(1,2) LCS(1,2) LCS(2,1) LCS(3,0) LCS(2,1) LCS(1,2) LCS(2,1) LCS(0,2) LCS(1,1) LCS(0,2) LCS(1,1) LCS(2,0) LCS(1,1) LCS(2,0) LCS(1,1) LCS(0,2) LCS(1,1) LCS(2,0) LCS(1,1) LCS(0,1) LCS(1,0) LCS(0,1) LCS(1,0) LCS(0,1) LCS(1,0) LCS(1,0) LCS(0,1) LCS(0,1) LCS(1,0) LCS(0,1) LCS(1,0) LCS(1,4) LCS(2,4) LCS(2,3) Call Tree LCS(0,4) LCS(1,3) LCS(1,3) LCS(2,2) LCS(0,3) LCS(1,2) LCS(0,3) LCS(1,2) LCS(1,2) LCS(2,1) LCS(0,2) LCS(1,1) LCS(0,2) LCS(1,1) LCS(0,2) LCS(1,1) LCS(2,0) LCS(1,1) LCS(0,1) LCS(1,0) LCS(0,1) LCS(1,0) LCS(0,1) LCS(1,0) - 37 - LCS(0,1) LCS(1,0) 한빛미디어
DP LCS(m, n) 두문자열 X m 과 Y n 의 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 (x m = y n ) 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) - 38 - 한빛미디어
문제예 5: Shortest Path Optional! Weighted digraph G=(V, E) w i,j : vertex i 에서 vertex j 에이르는 edge 의길이 목표 Edge 가없으면 시작점 s 에서다른각 vertex 에이르는최단거리를모두구한다 - 39 - 한빛미디어
d k t : 중간에최대 k 개의 edge를거쳐 s로부터 vertex t에이르는최단거리 목표 : d n-1 t Note! For i s, d 0 t = d 1 t = w s,t 다음페이지로넘어가기전에무엇을중심으로관계를파악할지스스로생각해보자 - 40 - 한빛미디어
Recursive Relation d tk = min {d r k-1 + w r, t } d 0 s = 0; d 0 t = ; for all edges (r, t) - 41 - 한빛미디어
DP Ballman-Ford(G, s) { d s 0; for all vertices i s d i ; for k 1 to n-1 { for all edges (a, b) { if (d a + w a,b < d b ) then d b d a + w a,b ; } a } } b ü Propagation 되는모습이떠오르면잘이해한것! - 42 - 한빛미디어
(a) 8 10 (b) i =1 8 8 10 (c) i =2 8-6 10 0-15 0-15 2 2 0-15 10 9 1 9 1 9 1 11 11 3-12 5 9 3-12 5 11 9 3-12 11 8 8 11 19 8 8-7 8-7 4 4 8-7 19 4 5 2 (f) i =5 0 11 11 8-15 10-15 1 9 1 0 3-12 9 8 8-7 10 4 5 2 (e) i =4 0 6 11 11 8-8 10-15 4 9 1 0 3-12 12 8 8-7 16 4 5 2 (d) i =3 0 6 11 11 8-6 10-15 4 9 1 7 3-12 12 8 8-7 19 4 5 2 12-43 - 한빛미디어
(f) i =5 0 11 11 8-15 10-15 1 9 1 0 3-12 9 8 8-7 10 4 5 2 6 나중에그래프알고리즘부분에서다시한번생각할기회가있음 (g) i =6 8-15 10 (h) i =7 8-18 10 (i) 8-18 10 0 11 11-15 1 9 1-3 3-12 3 8 8-7 10 4 5 2 3 0 11 11-15 -5 9 1 9 3-12 3 8 8-7 7 4 5 2 6 11 0 11-15 -5 9 1 9 3-12 3 8 8-7 7 4 5 2 6-44 - 한빛미디어
IT COOKBOOK Thank you - 45 - 한빛미디어