[Chapter5] 동적 계획 알고리즘

Dynamic Programming(DP) 알고리즘

: 입력 크기가 작은 부분 문제들 해결 -> 그 해들을 이용해 보다 큰 크기의 부분 문제들 해결 -> 최종적으로 원래 주어진 입력의 문제 해결

 

- 최적성의 원리: 큰 문제를 해결하기 위해서는 작은 문제들이 해결되어야 한다.

- 최적화 구조: 그런 구조를 가짐

 

그리디와 DP는 모두 최적성 원리&최적화 구조 가지고 있음

그리디 알고리즘과 DP는 모두 최적해를 구하는 것이 목적

그리디는 0-1의 경우 최적해 보장이 안 되지만, DP는 항상 최적해를 보장해준다.

 

	그리디 알고리즘	DP
목적	최적해 구하기 (최적성 원리 & 최적화 구조)
최적해 항상 보장?	X (0-1의 경우 안 됨)	O

 

	분할 정복 알고리즘	DP 알고리즘
해 구하는 과정
해 중복 가능 여부	부분 문제의 해 중복 x	부분 문제들 사이 의존적 관계

 

모든 쌍 최단 경로 문제

1. 다익스트라 알고리즘

: 각 점을 시작점으로 정해 Dijkstra 알고리즘 여러 번 수행

- 시간 복잡도: O(n^3), 단, n은 점의 수

- 음수 가중치 반영 x (한 번 확정했다면 되돌릴 수 없음)

 

2. 플로이드-워샬 알고리즘

: 시간 복잡도는 O(n^3)으로 다익스트라 알고리즘과 동일하지만,

- 코드는 아래처럼 훨씬 간단

- 음수 가중치 반영 o (덮어쓸 수 있음)

 

아이디어

 

:3개의 점이 있는 경우, a에서 c까지의 최단 경로를 찾으려면 2가지 경로, 즉, a에서 c로 직접 가는 경로와 점 b를 경유하는 경로 중 짧은 것 선택

 

경유 가능한 점이

- 점 1

- 점 1,2

- 점 1,2,3

...

- 점 1,2,...,n 일 때

모든 점을 경유 가능한 점들로 고려하면서, 모든 쌍의 최단 경로의 거리 계산

 

부분 문제의 정의

𝐷𝑖𝑗𝑘 = 점 {1, 2,⋯, 𝑘}를 경유 가능한 점으로 고려하여, 점 𝑖에서 점 𝑗까지의 모든 경로 중 가장 짧은 경로의 거리
 = 점 i에서 점 k를 경유하여 j로 가는 경로의 거리와 Dij(k-1) 중 더 짧은 경로의 거리
 = min{Dij(k-1), Dik(k-1)+Dkj(k-1)}

- 점 1에서 점 𝑘까지의 모든 점을 반드시 경유하는 경로를 의미하는 것이 아니다.

- 𝐷𝑖𝑗𝑘 는 {1, 2,⋯, 𝑘}을 하나도 경유하지 않으면서 점 𝑖에서 직접 점 𝑗에 도달하는 간선 (𝑖, 𝑗)가 가장 짧은 거리일수도 있음

- 단, 𝑘 ≠ 𝑖, 𝑘 ≠ 𝑗이고 𝑘 = 0인 경우, 점 0은 그래프에 없으므로 어떤 점도 경유하지 않는다는 것을 의미.

=> 𝐷𝑖𝑗0 = 간선 (𝑖, 𝑗)의 가중치

 

알고리즘

AllPairsShortest
입력: 2차원 배열 D, 단, D[i,j]=간선 (i,j)의 가중치, 만일 간선 (i,j)가 없으면 D[i,j] = ∞, 모든 i에 대하여 D[i,i] = 0
출력: 모든 쌍 최단 경로의 거리를 저장한 2차원 배열 D
1. for k=1 to n
2. 	for i=1 to n (i≠k)
3. 		for j=1 to n (j≠k, j≠i)
4. 			D[i,j] = min{D[i,k]+D[k,j], D[i,j]}

 

D[i,j]를 계산하기 위해 D[i,k]와 D[k,j]가 미리 계산되어 있어야 함

- Line 2~3: 인접행렬을 모두 채우는 과정

- k=1~n 업데이트

* min{D[i,k]+D[k,j], D[i,j]} 반복 수행

 

수행 과정

 

다음과 같은 그래프가 있을 때

1. 행렬로 변환

이 그래프는 다음과 같은 인접 행렬로 만들어질 수 있다.(만들 수 있어야 함!!)

- 자신에서 자신으로 가는 간선은 모두 '1'

- 간선 없으면 '∞'

2. min{Dik+Dkj, Dij}

 

- D1

 

- D2

 

- D3

- D4

- D5

 

시간 복잡도

 

반복문 3번 => O(n^3)

 

연속 행렬 곱셈

 

연속된 행렬들의 곱셈에 필요한 원소 간 최소 곱셉 횟수 찾기

ex. A(10 x 20) & B(20 x 5)

=> 곱셈 횟수: 10 x 20 x 5 = 1000

 

행렬곱셈은..

- 결합법칙 가능

* (AxB)xC: 10x20x5(A,B의 곱) + 10x5x15(AB와 C의 곱) = 1750

* Ax(BxC): 20x5x15(B,C의 곱) + 10x20x15 = 4500

- 교환법칙 불가(순서가 있기 때문)

 

 

알고리즘

 

 

 

수행 과정

1. 행렬로 표시해두기

2. 묶지 않았을 때(L=1)

 

3. 두 개씩 묶었을 때(L=2)

(1) i=1: A1 & A2 & A3

- k=1: (A1xA2)xA3 

- k=2: A1x(A2xA3)

 

(2) i=2: A2 & A3 & A4

- k=2: A2x(A3xA4)

- k=3: (A2xA3)xA4

 

4. 세 개씩 묶었을 때(L=3)

 

 

시간 복잡도

 

총 부분 문제 수: (n-1)+(n-2)+...+2+1=n(n-1)/2

하나의 부분 문제는 k-루프가 최대 (n-1)번 수행

=> O(n^3)

편집 거리 문제

 

편집 거리: 삽입, 삭제, 대체 연산을 사용해 스트링 S를 수정하여 다른 스트링 T로 변환하고자 할 때 필요한 최소의 편집 연산 횟수

 

다음 예제를 살펴보자.

"strong -> stone"

 

- 's'와 't'는 그대로 사용

- 'r'을 삭제

- 'o'와 'n'을 그대로 사용

- 'g'를 'e'로 대체

=> 총 2회의 편집 연산만 수행(최소 편집 횟수)

 

부분 문제 정의

 

|S|=m, |T|=n일 때

E[i,j] = S의 처음 i개 문자를 T의 처음 j개 문자로 바꾸는 데 필요한 편집 거리

 

ex. 'strong'->'stone'에 대해, 'stro'를 'sto'로 바꾸기 위한 편집 거리는 E[4,3]

 

- s1->t1['s' => 's']: s1=t1='s'->E[1,1]=0

- s1->t1t2['s'=>'st']: s1=t1='s'이고, 't'를 삽입하므로 E[1,2]=1

- s1s2->t1['st'=>'s']: s1=t1='s'이고, 't'를 삭제하여 E[2,1]=1

- s1s1->t1t2['st'=>'st']: s1=t1='s'이고, s2=t2='t'이므로 E[2,2]=0

 

<E[4,3]를 구하기 위해서는>

 

E[i,j] = min{E[i,j-1]+1, E[i-1,j]+1, E[i-1, j-1]+𝛼}
단, if 𝑠𝑖 ≠ 𝑡𝑗 𝛼 = 1 𝑒𝑙𝑠𝑒 𝛼 = 0

 

이때 삽입, 삭제는 1만큼의 거리가 들고, 변경은 모른다.

 

1. E[4,2]의 해를 안다면, t3='o'를 삽입 -> E[4,2]+1=3

* 2개만 채워져 있으므로 하나를 삽입해야 함

2. E[3,3]의 해를 안다면, s4='o'를 삭제 -> E[3,3]+1=2

* 3개 모두 채워져 있으므로 삭제해주면 됨

3. E[3,2]의 해를 안다면, s4='o'과 t3='o'이 같으므로 E[3,2]+1=1

 

=> 3번 방법을 고름 !

 

알고리즘

 

입력: 스트링 S, t, 단, S와 T의 길이는 각각 m과 n이다.
출력: S를 T로 변환하는 편집 거리, E[m,n]
1. for i=0 to n E[i,0]=i 
2. for j=0 to n E[0,j]=j
3. for i=1 to m
4. 	for j=1 to n
5.		E[i,j]=min{E[i,j-1]+1,E[i-1,j]+1, E[i-1,j-1]+α} //여기가 중요
6. return E[m,n]

 

if Si==Tj then E[i,j]=E[i-1,j-1]
else E[i,j]=min{E[i,j-1], E[i-1,j], E[i-1, j-1]}

수행 과정

 

최종 출력횟수에서 거슬러 올라가면 편집 과정을 알 수 있다.

삽입: 왼쪽->오른쪽

삭제: 위->아래

대체: 대각선

 

시간 복잡도

 

O(mn)

*m과 n은 두 스트링의 각각의 길이

 

Longest Common Sequence(LCS)

 

다음과 같이 같은 것을 찾아나가는 것

(<-> 편집 거리 문제는 다른 것 찾아나가는 문제)

같으면: 위대각선+1

다르면: max

 

위는 비연속일 때고, 연속일 때도 해보라 하셨음

 

배낭 문제

 

Fractional knapsack 문제는 최적해를 구할 수 있어 그리디 알고리즘만으로 가능했지만

0-1문제는 최적해가 불가능하기 때문에 동적 계획 알고리즘을 사용해야 한다.

 

<문제의 요소>

1. 물건

2. 물건의 무게

3. 물건의 가치

4. 배낭의 용량

=> 1. 물건 & 2. 물건의 무게 -> 부분 문제 정의에 사용

 

K[i,w] = 물건 1~i까지만 고려, 배낭의 용량=w일 때의 최대 가치
단, i=1,2,...,n이고 w=1,2,...,C

 

for i=0 to n K[i,0]=0 //배낭의 용량이 0일 때
for w=0 to C K[0,w]=0 // 물건 0 = 어떤 물건도 고려하지 않을 때
for i=1 to n
	for w=1 to C // w = 배낭의 임시 용량
    		if(wi>w) //물건 i의 무게가 임시 배낭 용량을 초과하면
        		K[i,w] = K[i-1,w] // 위의 값 그대로 씀
        	else  //초과하지 않으면 (물건 i를 배낭에 담지 않을 경우와 담을 경우 고려)
        		K[i,w] = max{K[i-1,w],K[i-1,w-wi]+vi} //앞: 담지 않을 경우 / 뒤: 담을 경우
return K[n,C]

 

수행 과정

 

 

(Line1~2) 0번 행과 0번 열의 각 원소를 0으로 초기화

 

=> 담지 않을 경우(K[i-1,w]) vs 담을 경우(K[i-1, w-wi]+vi) 중 큰 값 써줌

* 담지 않을 경우(K[i-1,w]): 바로 위

* 담을 경우(K[i-1, w-wi]+vi): 위쪽에서 무게만큼 뺀 인덱스 + 가치

 

예제

 

Q)

A)

시간 복잡도

 

- 1개의 부분 문제에 대한 해를 구할 때: O(1)

- 부분 문제 수: 배열 K의 원소 수 = n*C

=> O(1)*n*C=O(nC)

 

동전 거스름돈 문제

 

대부분의 경우 그리디 알고리즘으로 해결되지만 해결 못하는 경우도 있음

-> DP 알고리즘은 모든 동전 거스름돈 문제에 대해 항상 최적해 찾음

 

문제에 주어진 요소들

- 동전의 종류 d1,d2,...,dk (단, d1>d2>...>dk=1)

-거스름돈 n원

 

=> 배낭 문제의 DP 알고리즘에서 배낭의 용량을 1kg씩 증가시켜가며 문제 해결

 

부분 문제

 

C[1] = 1원을 거슬러 받을 때 사용되는 최소 동전 수
C[2] = 2원을 거슬러 받을 때 사용되는 최소 동전 수
...
C[n] = n원을 거슬러 받을 때 사용되는 최소 동전 수

 

<C[j] 계산하는 데 어떤 부분 문제가 필요?>

C[j] = min_(1<=i<=k){C[j-di]+1} if j>=di
* C[j-di]: 이미 계산된 부분문제의 최적해
-> 'i: 동전의 종류' 이므로 각 동전에 대해 모두 계산해 최솟값 찾음
-> 액수(j)가 해당 동전의 액수보다 커야 추가 가능

 

ex.

- 500원 동전이 필요하다면 (j-500)원의 해, 즉, C[j-500]에다가 500원짜리 동전 1개 추가

- 100원 동전이 필요하다면 (j-100)원의 해, 즉, C[j-100]에다가 100원짜리 동전 1개 추가

- 50원 동전이 필요하다면 (j-50)원의 해, 즉, C[j-50]에다가 50원짜리 동전 1개 추가

- 10원 동전이 필요하다면 (j-10)원의 해, 즉, C[j-10]에다가 10원짜리 동전 1개 추가

- 1원 동전이 필요하다면 (j-1)원의 해, 즉, C[j-1]에다가 1원짜리 동전 1개 추가

 

알고리즘

 

입력: 거스름돈 n원, k개의 동전의 액면, d1>d2>...>dk=1
출력: C[n]
1. for i=1 to n C[i] = ∞ //초기화
2. C[0]=0
3. for j=1 to n //j는 1원부터 증가하는 (임시) 거스름돈 액수
4. 	for i=1 to k
5.		if (di<=j) and (C[j-di]+1 < C[j]) // 동전 고려 여부 & 이미 계산된 문제의 최적해
6.			C[j] = C[j-di]+1 //min(이미 계산된 해, 동전 넣었을 때 값)
7. return C[n]

 

 

좀 복잡하기 때문에 4개만 예를 들어 써보겠다.

형광펜으로 묶어놓은 4개의 그룹들 중 하나씩.(0 제외)

 

1. j=4일 때

=> 

(4-1)

-> 3+1=4

 

2. j=9일 때

=> 

(9-1) vs (9-5)

-> 4 vs 4 중 작은 값

-> 4+1=5

 

3. j=15일 때

=> 

(15-1) vs (15-5) vs (15-10)

-> 5 vs 1 vs 1 중 작은 값

-> 1+1=2

 

4. j=20일 때

=> 

(20-1) vs (20-5) vs (20-10) vs (20-16)

-> 4 vs 2 vs 1 vs 4 중 작은 값

-> 1+1=2

 

=> (외우기)1. DP 알고리즘은 부분 문제들 사이의 관계를 빠짐없이 고려하여 문제를 해결

2. DP 알고리즘은 최적 부분 구조 또는 최적성 원칙 특성을 가짐

: 문제의 최적해 속에 부분 문제의 최적해가 포함돼 있다.

그리디 알고리즘도 같은 속성 가짐

 

시간 복잡도

 

O(nk)

: 거스름돈 j가 1~n원까지 변하며, 각각의 j에 대해서 최대 모든 동전 (d1, d2, ..., dk)을 1번씩 고려하기 때문

 

시간복잡도 비교

	플로이드	연속 행렬 곱셈	편집 거리 문제	배낭 문제	동전 거스름돈 문제
시간 복잡도	O(n^3) * 1 * 1,2 ... *1,2,...n 모든 쌍의 최단 경로 거리 계산	O(n^3) 이웃하는 행렬들끼리 곱하는 모든 부분 문제 해결하여 최적해 찾음	O(mn) * m,n: 두 스트링의 길이	O(nC) * i: 1~n * w: 1~C	O(nk) * n: 거스름돈 액수 * k: 동전 종류 수

 

 

이진 힙

 

우선순위 큐를 구현하는 가장 기본적은 자료구조

* 우선순위 큐: 가장 높은 우선순위를 가진 항목에 접근, 삭제와 임의의 우선순위를 가진 항목을 삽입을 지원하는 구조

 

스택/힙도 일종의 우선순위 큐

- 스택: 가장 마지막으로 삽입된 항목이 가장 높은 우선순위 -> 최근 시간일수록 높은 우선순위

- 큐: 먼저 삽입된 항목이 더 높은 우선순위 -> 이른 시간일수록 더 높은 우선순위

 

이진힙: 완전 이진트리로서 부모의 우선순위가 자식의 우선순위보다 높은 자료구조

- min heap: 작은 숫자일수록 더 높은 우선순위

- max heap: 큰 숫자일수록 더 높은 우선순위

=> 형제관계는 중요x, 단지 부모자식 관계만 맞으면 ok

 

 

최솟값 삭제

: downheap

 

삽입 연산

 

: upheap