제8장 동적 프로그래밍

http://academy.hanb.co.kr

쉽게 배우는 알고리즘

8장. 동적 프로그래밍

8장.

동적 프로그래밍

Dynamic Programming (DP)

- 3 - 한빛미디어㈜

학습목표

• 동적 프로그래밍이 무엇인가

를 이해한다.

• 어떤 특성을 가진 문제가 동적 프로그래밍의

적용 대상인지를 감지

할 수 있도록 한다.

• 기본적인 몇 가지 문제를 동적 프로그래밍으

로 해결할 수 있도록 한다.

배경

• 재귀적 해법

– 큰 문제에 닮음꼴의 작은 문제가 깃든다.

– 잘 쓰면 보약, 못쓰면 맹독

• Dynamic Programming

– 재귀적 중복을 해결하는 프로그래밍 기법

– 이 기법에 왜 동적 프로그래밍이라는 이름이

- 5 - 숙명여대 멀티미디어과학과

재귀적 해법의 빛과 그림자

• 재귀적 해법이 바람직한 예

– 퀵정렬, 병합정렬 등의 정렬 알고리즘

– 계승(factorial) 구하기

– 그래프의 Depth First Search

– …

• 재귀적 해법이 치명적인 예 è DP의 대상!!

– 피보나치수 구하기

– 행렬곱셈 최적순서 구하기

– …

도입문제: 피보나치수 구하기

• f

_n

= f

_n-1

+ f

_n-2

• 아주 간단한 문제지만

– Dynamic programming의 동기와 구현이 다

포함되어 있다.

- 7 - 숙명여대 멀티미디어과학과

피보나치수를 구하는 Recursive Algorithm

fib

(n)

{

if

(n == 1 or

n == 2)

then return

1;

else return

(

fib

(n-1) +

fib

(n-2));

}

ü

엄청난 중복 호출이 존재한다

피보나치 수열의 Call Tree

- 9 - 숙명여대 멀티미디어과학과

fib()에서 문제 크기가 커짐에 따라

중복 호출이 증가하는 모습

ü

중복 호출 횟수 자체가 다시 피보나치 수열을 이루며 증가

ü

증가 속도는 2

이상의 비율

피보나치수를 구하는 DP Algorithm

fib(n)

{

f[1] = f[2] = 1;

for

(i = 3; i <= n; i++)

f[i] = f[i-1] +f[i-2];

return

f[n];

}

ü

Θ(n) 시간에 끝난다

- 11 - 숙명여대 멀티미디어과학과

피보나치수 DP 재귀 버전

è Memoization(메모하기) 기법에 해당.

DP의 적용 요건

• Optimal substructure

– 큰 문제의 최적 솔루션에 작은 문제의 최적

솔루션이 포함됨

• Overlapping recursive calls

– 재귀적 해법으로 풀면 같은 문제에 대한

재귀호출이 심하게 중복됨

- 13 - 숙명여대 멀티미디어과학과

문제 예 2: 행렬 경로 문제

• 양 또는 음의 정수 원소들로 구성된 n×n 행렬이

주어지고, 행렬의 좌상단에서 시작하여 우하단까지

이동한다

• 이동 방법 (제약조건)

• 목표: 행렬의 좌상단에서 시작하여 우하단까지

이동하되, 방문한 칸에 있는 수들을 더한 값이

최대화되도록 한다

불법 이동의 예

- 15 - 숙명여대 멀티미디어과학과 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

유효한 이동의 예

• 변수 c

: 원소 (i, j)에 이르는 최고점수

• c

=







+ 



+ 



+ max {



}

if i == j == 1

if i == 1, j > 1

if i > 1, j == 1

if i > 1, j > 1

행렬 경로 문제의 Recursive Algorithm

if(i == 1 andj == 1) then returnmij;

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);

- 17 - 숙명여대 멀티미디어과학과 mat(4,3) mat (4,2) mat(3,3) mat(3,2) mat(4,1) mat(2,1) mat(3,1) mat(1,1) mat(3,1) mat(2,2) mat(4,4) mat(2,3) mat(1,2) mat(2,1) mat(1,1) mat(2,1) mat(1,2) mat(1,1) mat(1,1) mat(1,1) mat(3,4) mat(2,4) mat(2,3) mat(1,4) mat(1,2) mat(1,3) mat(1,1) mat(1,3) mat(2,2) mat(1,2) mat(1,1) mat(1,2) mat(2,1) mat(1,1) mat(1,1) mat(1,3) mat(3,2) mat(3,1) mat(2,2) mat(2,1) mat(1,1) mat(2,1) mat(1,2) mat(1,1) mat(1,1) mat(2,2) mat(2,1) mat(1,2) mat(1,1) mat(1,1) mat(3,3) mat(2,3) mat(1,2) mat(1,1) mat(1,3) mat(3,2) mat(3,1) mat(2,2) mat(2,1) mat(1,1) mat(2,1) mat(1,2) mat(1,1) mat(1,1) mat(2,2) mat(2,1) mat(1,2) mat(1,1) mat(1,1)

Call Tree

matrixPath()에서 문제 크기가 커짐에

따라 중복 호출이 증가하는 모습

- 19 - 숙명여대 멀티미디어과학과

DP

c[i, j] ← m_ij+ max(c[i-1, j], c[i, j-1]);

returnc[n, n]; }

üComplexity: O(n

₎

문제 예 3: 조약돌 놓기

• 3×N 테이블의 각 칸에 양 또는 음의 정수가 기록되어

있다

• 조약돌을 놓는 방법 (제약조건)

• 목표: 돌이 놓인 자리에 있는 수의 합을 최대가 되도록

조약돌 놓기

- 21 - 숙명여대 멀티미디어과학과

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!

- 23 - 숙명여대 멀티미디어과학과 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 6 7 12 -5 5 3 11 3 -8 10 14 9 7 13 8 5 11 12 7 4 8 -2 9 4 패턴 1: 패턴 2: 패턴 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:

가능한 패턴

서로 양립할 수 있는

패턴들

- 25 - 숙명여대 멀티미디어과학과

6

7

12

-5

5

3

11

3

-8

10

14

9

7

13

8

5

11

12

7

4

8

-2

9

4

…

-5

…

4

-5

…

4

i

i-1

• c

: i 열이 패턴 p로 놓일 때의 최고점수

• w

: i 열이 패턴 p로 놓일 때 i열에 돌이 놓인 곳의 점수

합

• c

=





max 

 + 

if i == 1

if i > 1

단, q는 p와 양립 가능한

패턴 q

Recursive Algorithm

return(w[i, p] + max) ; }

- 27 - 숙명여대 멀티미디어과학과 pebbleSum(n)

▷ n 열까지 조약돌을 놓은 방법 중 최대 점수 합 구하기

{

return max { pebble(n, p) } ; }

ü pebble(i, 1) ~ pebble(i, 4) 중 최대값이 최종적인 답

p =1,2,3,4

peb(4,3)

peb (3,1) peb(3,2) peb(2,3) peb(2,1) peb(1,1)peb(1,3) peb(1,4) peb(1,1) peb(1,2) peb(1,2) peb(1,3)

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

Call Tree

- 29 - 숙명여대 멀티미디어과학과

pebble()에서 문제 크기가 커짐에 따라

중복 호출의 비율이 증가하는 모습

DP 적용

• DP의 요건 만족

– Optimal substructure

– Overlapping recursive calls

• 함수 pebble() 한 번 호출은 부분 문제 한 개와

대응됨

– 이 4n개를 아래에서 작은 것부터 저장해가며

구하면 됨.

- 31 - 숙명여대 멀티미디어과학과

DP

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

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] ← w[i, p] + max {peb[i-1, q]} ;

}

return

max {

peb

[n, p] } ;

}

패턴 q는 패턴 p와 양립

- 33 - 숙명여대 멀티미디어과학과

문제 예 4: 행렬 곱셈 순서(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

, A

, A

, …, A

을 곱하는 최적의 순서는?

Recursive Relation

• 마지막으로 matrix multiplication이 수행되는 상황

– n-1 가지 가능성

– 어느 경우가 가장 매력적인가?

- 35 - 숙명여대 멀티미디어과학과

ü c

: 행렬 A

, A

, …, A

의 곱 A

A

…A

를 계산하는

최소 비용

ü A

의 차원: p

p

0

if i == j

min {c

+ c

+ p

p

p

}

if i < j

c

=

Recursive Algorithm

q = rMatrixChain(i, k) + rMatrixChain(k+1, j) + pi-1pkpj;

if(q < min) thenmin = q; }

- 37 - 숙명여대 멀티미디어과학과

DP

m[i, j] ← min {m[i, k] + m[k+1, j] + pi-1pkpj};

} returnm[1, n]; } i ≤ k ≤ j-1

ü

Complexity: Θ(n

₎

문제 예 5: 최장 공통부분 순서

Longest Common Subsequence(LCS)

• 두 string에 공통적으로 들어있는 common

subsequence들 중 가장 긴 것을 찾는다

• Subsequence의 예

– <bcdb>는 문자열 <abcbdab>의 subsequence이다

• Common subsequence의 예

– <bca>는 문자열 <abcbdab>와 <bdcaba>의 common subsequence이다

• Longest common subsequence(LCS)

– Common subsequence들 중 가장 긴 것

- 39 - 숙명여대 멀티미디어과학과

Optimal Substructure

• 두 문자열 X

= <x

x

… x

>과 Y

= <y

y

… y

>에 대해

• c

=

x

== y

max{

x

y

ü

c

Recursive Algorithm

else if(xm== yn) then returnLCS(m-1, n-1) + 1;

else returnmax{LCS(m-1, n), LCS(m, n-1)}; }

- 41 - 숙명여대 멀티미디어과학과 LCS(3,4) LCS(3,3) LCS(2,4) LCS(1,4) LCS(1,3) LCS(0,4) LCS(1,2) LCS(0,3) LCS(1,1) LCS(0,2) LCS(0,1) LCS(1,0) LCS(2,3) LCS(2,2) LCS(2,1) LCS(1,3) LCS(1,2) LCS(0,3) LCS(1,1) LCS(0,2) LCS(0,1) LCS(1,0) LCS(1,2) LCS(1,1) LCS(0,2) LCS(0,1) LCS(1,0) LCS(1,1) LCS(2,0) LCS(0,1) LCS(1,0) LCS(3,2) LCS(2,2) LCS(2,1) LCS(3,1) LCS(2,1) LCS(3,0) LCS(1,1) LCS(2,0) LCS(1,0) LCS(0,1) LCS(1,2) LCS(1,1) LCS(0,2) LCS(0,1) LCS(1,0) LCS(1,1) LCS(2,0) LCS(0,1) LCS(1,0) LCS(2,3) LCS(2,2) LCS(2,1) LCS(1,3) LCS(1,2) LCS(0,3) LCS(1,1) LCS(0,2) LCS(0,1) LCS(1,0) LCS(1,2) LCS(1,1) LCS(0,2) LCS(0,1) LCS(1,0) LCS(1,1) LCS(2,0) LCS(0,1) LCS(1,0)

Call Tree

LCS()에서 문제 크기가 커짐에 따라

중복 호출이 증가하는 모습

- 43 - 숙명여대 멀티미디어과학과

DP

if(xm== yn) thenC[i, j] = C[i-1, j-1] + 1;

elseC[i, j] = max{C[i-1, j], C[i, j-1]};

returnC[m, n]; }

ü

Complexity: Θ(mn)

문제 예 6: Shortest Path

• Weighted digraph G=(V, E)

– w

: vertex i에서 vertex j에 이르는 edge의 길이

• Edge가 없으면 ∞

• 목표

– 시작점 s에서 다른 각 vertex에 이르는 최단거리를

모두 구한다

- 45 - 숙명여대 멀티미디어과학과

• d

_{: 중간에 최대 k 개의 edge를 거쳐}

s로부터 vertex t에 이르는 최단거리

• 목표: d

• Note! For i≠s,

– d

_{= ∞}

– d

_{= w}

Recursive Relation

d

_t

k

_{= min {}

_d

r

k-1

+ w

r, t

}

d

_s

0

_{= 0;}

d

_t

0

_{= ∞;}

- 47 - 숙명여대 멀티미디어과학과

DP

Ballman-Ford(G, s) {

ds← 0;

forall vertices i ≠ s di← ∞;

fork ← 1 ton-1 {

forall edges (a, b) {

if(da+ wa,b< db ) thendb ← da+ wa,b;

} } } ü Propagation 되는 모습이 떠오르면 잘 이해한 것! b a 8 9 8 10 1 3 -12 -7 11 8 2 4 5 -15 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ (a) 8 9 8 10 1 3 -12 -7 11 8 2 4 5 -15 0 ∞ 11 9 ∞ ∞ 8 ∞ (b) i =1 8 9 8 10 1 3 -12 -7 11 8 2 4 5 -15 0 19 11 9 19 10 -6 ∞ (c) i =2 8 9 10 1 3 -12 11 8 2 5 -15 0 11 7 12 4 -6 12 (d) i =3 8 9 10 1 3 -12 11 8 2 5 -15 0 11 0 12 4 -8 6 (e) i =4 8 9 10 1 3 -12 11 8 2 5 -15 0 11 0 9 1 -15 6 (f) i =5

- 49 - 숙명여대 멀티미디어과학과 8 9 8 10 1 3 -12 -7 11 8 2 4 5 -15 0 10 11 0 9 1 -15 6 (f) i =5 8 9 8 10 1 3 -12 -7 11 8 2 4 5 -15 0 7 11 9 3 -5 -18 6 (i) (h) i =7₈ 9 8 10 1 3 -12 -7 11 8 2 4 5 -15 0 7 11 9 3 -5 -18 6 8 9 8 10 1 3 -12 -7 11 8 2 4 5 -15 0 10 11 -3 3 1 -15 3 (g) i =6 나중에 그래프 알고리즘 부분에서 다시 한 번 생각할 기회가 있음 IT COOKBOOK IT COOKBOOK

Thank you