[알고리즘 분석] 03 - 1 동적계획(Dynamic Programming)

동적계획

divide-and-conquer(분할정복식, 재귀) 알고리즘은 하향식(top-down) 해결법

• 나누어진 부분들 사이에 서로 상관관계가 없는 문제를 해결하는데 적합

피보나찌 알고리즘은 나누어진 부분들이 서로 연관이 있음.

• 같은 항 f(i) 를 한 번 이상 -> 비효율적
• 분할정복식 방법은 적합하지 않음.

동적계획법(dynamic programming)은 상향식 해결법(bottom-up approach)

• 분할정복식 방법과 마찬가지로 문제를 나눈 후에 나누어진 부분들을 먼 저 푼다.
• 인덱스를 효과적으로 설정하여 작은 문제들의 중복해결을 배제
• 작은 문제 해결을 먼저
• 결과를 큰 문제의 해결로 확산
• 개발 절차

(1) 재귀 관계식(recursive property) 정립

(2) 작은 사례를 먼저 해결하는 상향식 방법으로 진행

 

이항계수 구하기

• 이항계수(binomial coefficient) 공식

• 계산량이 많은 n!이나 k!을 계산하지 않고 이항계수를 구하기 위해서 다음 식을 사용한다.(100! ?)

알고리즘: 분할정복식 접근방법

문제: 이항계수를 계산한다.

입력: 음수가 아닌 정수 n과 k, 여기서 k ≤ n

출력: bin, nCk

알고리즘:

알고리즘: 분할정복식 접근방법

시간복잡도 분석:

• 분할정복 알고리즘은 작성하기는 간단하지만, 효율적이지 않다.
• 이유? : 알고리즘을 재귀호출(recursive call)할 때 같은 계산을 반복해서 수행하 기 때문이다.
• 예를 들면, bin(n-1,k-1)과 bin(n-1,k)는 둘 다 bin(n-2,k-1) 의 결과가 필요한데, 따로 중복 계산됨
• nCk를 구하기 위해서 이 알고리즘이 계산하는 항(term)의 개수는 2 × nCk - 1 이다.

nCk를 구하기 위해서 이 알고리즘이 계산하는 항(term)의 개수는 2 × nCk - 1 이다.

• 증명: (n에 대한 수학적귀납법으로 증명)
• 귀납출발점: 항의 개수 n이 1일 때 2×nCk-1=2×1-1=1 이 됨을 보이면 된다. 1Ck 는 k = 0 이나 1 일 때 1이므로 항의 개수는 항상 1이다.
• 귀납가정: nCk를 계산하기 위한 항의 개수는 2×nCk-1 이라고 가정한다.
• 귀납절차: n+1Ck 를 계산하기 위한 항의 개수가 2×n+1Ck-1임을 보이면 된다. 알고리 즘에 의해서 n+1Ck = nCk-1+ nCk 이므로, 즉 n+1Ck를 계산하기 위한 항의 총 개수는 nCk-1 를 계산하기 위한 총 개수와 nCk를 계산하기 위한 항의 총 개수에다가 이 둘을 더하 기 위한 항 1을 더한 수가 된다. 그런데 nCk-1 를 계산하기 위한 항의 개수는 가정에 의해서 2×nCk-1-1 이고, nCk를 계산하기 위한 항의 개수는 가정에 의해서 2×nCk-1 이다. 따라서 항의 총 개수는

 

동적계획식 알고리즘 설계전략

1. 재귀 관계식(recursive property)을 정립:

- 2차원 배열 B를 만들고, 각 B[i][j]에는 i Cj 값을 저장하도록 함

- 그 값은 다음과 같은 관계식으로 계산

2. nCk를 구하기 위해서는 다음과 같이 B[0][0]부터 시작하여 위에서 아래로 재귀 관계식을 적용하여 배열을 채워 나가면 된다. 결국 값은 B[n][k] 에 저장된다.

 

동적계획 알고리즘

• 문제: 이항계수를 계산한다.
• 입력: 음수가 아닌 정수 n과 k, 여기서 k ≤ n
• 출력: bin2, nCk

 

동적계획 알고리즘의 분석

• 단위연산: for-j 루프 안의 문장
• 입력의 크기: n, k

 

그래프 용어

• 정점(vertex, node), 이음선(edge, arc)
• 방향 그래프(directed graph/digraph)
• 가중치(weight), 가중치 포함 그래프(weighted graph)
• 경로(path): 각 정점에서 다음 정점을 잇는 이음선이 존재하는 일련의 정 점들.
• 단순경로(simple path) – 같은 정점을 두 번 지나지 않는 경로
• 순환(cycle) – 한 정점에서 다시 그 정점으로 돌아오는 경로
• 순환 그래프(cyclic graph) vs 비순환 그래프(acyclic graph)                                                                        - - cycle이 있는(없는) 그래프
• 길이(length): 경로상에 있는 가중치의 합(가중치포함그래프). 경로상의 이음 선의 개수(가중치가 없는 그래프)

 

가중치 포함 방향 그래프의 예

 

최단경로 문제 (all-pairs shortest paths problem)

• 보기 : 모든 도시에 대해, 한 도시에서 다른 도시로 갈 수 있는 가장 짧은 길 을 찾는 문제
• 문제: 가중치 포함, 방향성 그래프에서 최단경로 찾기
• 최적화문제(optimization problem)                                                                                                      - 주어진 문제에 대하여 하나 이상의 많은 해답이 존재할 때, 이 가운데에 서 가장 최적인 해답(optimal solution)을 찾아야 하는 문제를 최적화문제 (optimization problem)라고 한다.
• 최단경로 찾기 문제는 최적화문제에 속한다.

 

 

동적계획식 설계전략 - 자료구조

• 그래프의 인접행렬(adjacency matrix)식 표현: W

• 그래프에서 최단경로의 길이의 표현:

D(k) [i][ j] =집합{v1,v2 ,...,vk}의

정점들 만을 이용해서(이들을 모두 이용해야 하는 것은 아님. 일부만 이용 가능) vi 에서 vj 로 가는 최단경로의 길이

• W : 그림 3.2에 있는 그래프의 인접행렬식 표현(문제)
• D : 각 정점들 사이의 최단 거리(답)

- D(0) = W 이고, D(n) = D

- D를 구하기 위해서는 D(0)를 가지고 D(n) 을 구할 수 있는 방법을 고안해 내어야 한다.

 

(예 3.2) 0 ≤ k ≤ 5 일 때, D(k) [2][5]?

• (1) D(0)[2][5] = length[v2, v5]=∞
• (2) D(1)[2][5] = min(length[v2, v5], length[v2, v1,v5]) = min(∞ , 14) = 14
• (3) D(2)[2][5] = D(1)[2][5]=14
• (4) D(3)[2][5] = D(2)[2][5]=14
• (5) D(4)[2][5] = min(length[v2, v1,v5], length[v2, v4,v5], length[v2, v1, v4, v5], length[v2, v3, v4,v5]), = min(14, 5, 13, 10) = 5
• (6) D(5)[2][5] = D(4)[2][5]=5

- 가능한 경로를 쉽게 확인할 수 있는 조직적인 방법 필요

 

동적계획식 설계절차

1. D(k-1)을 가지고 D(k) 를 계산할 수 있는 재귀 관계식(recursive property)을 정립

D(k) [i][j]=minimum{D(k-1)[i][j], D(k-1)[i][k]+ D(k-1)[k][j]}, (앞쪽이 경우1, 뒤쪽이 경우2)

경우 1: {v1, v2,…, vk}의 정점들 만을 통해서 vi 에서 vj 로 가는 최단경로가 vk 를 거치지 않는 경우.

(예) D(5)[1][3] = D(4)[1][3] = 3

경우 2: {v1, v2,…, vk}의 정점들 만을 통해서 vi 에서 vj 로 가는 최단경로가 vk 를 거치는 경우.

(예) D(2)[5][3] = D(1)[5][2] + D(1)[2][3] = 4 + 3 = 7

 

2. 상향식으로 k = 1부터 n까지 다음과 같이 이 과정을 반복하여 해를 구한 다.

D(0) , D(1) ,……., D(n)

(1) D(1)[2][4] = min(D(0)[2][4], D(0)[2][1]+D(0)[1][4]) = min(2, 9+1) = 2

(2) D(1)[5][2] = min(D(0)[5][2], D(0)[5][1]+D(0)[1][2]) = min(∞, 3+1) = 4

(3) D(1)[5][4] = min(D(0)[5][4], D(0)[5][1]+D(0)[1][4]) = min(∞, 3+1) = 4

D(1)을 모두 계산한 후 D(2)를 계산한다.

D(2)[5][4] = min(D(1)[5][4], D(1)[5][2]+D(1)[2][4]) /* D(1)사용 */ = min(4, 4+2) = 4

D(2) , D (3) , D(4) , D(5) = D를 순차적으로 계산한다.

 

Floyd의 알고리즘 I

• 문제: 가중치 포함 그래프의 각 정점에서 다른 모든 정점까지의 최단 거리를 계산하라.
• 입력: 가중치 포함, 방향성 그래프 W와 그 그래프에서의 정점의 수 n.
• 출력: 최단거리의 길이가 포함된 배열 D

모든 경우를 고려한 분석:

• 단위연산: for-j 루프안의 지정문
• 입력크기: 그래프에서의 정점의 수 n

T(n) = n x n x n = n^3 ∈ O(n^3)

 

D[i][j] 계산 시 D[i][k], D[k][j]값이 사용됨. 만일 D[k] 계산 시 D[i][k], D[k][j] 값이 변경된다면, 별도의 D를 저장할 공간이 필요. 그러나 필요하지 않다.

 

[이유]

• 추가 공간 필요 없이 D만을 이용하여 데이터 저장 가능                                                                              (이유) k번째 행과 k번째 열에 있는 값들이 루프의 k번째 반복을 수행하는 동안 변하 지 않기 때문                        D[i][k] = min(D[i][k], D[i][k]+D[k][k]);                                                                                                D[k][j] = min(D[k][j], D[k][k]+D[k][j]);

• 이 element 계산시 Dk-1[i,k], Dk-1[k,j] 필요. 그런데 이것은 Dk-1[i,k]= Dk[i,k], Dk-1[k,j] =Dk [k,j] . 따라서 overwrite 가능.
• (1)은 (2) 보다 먼저 계산. (1) 계산 시 (2)의 값이 필요. (2)의 값이 update되면 이미 계산된 (1)의 값이 달라짐. 그러나, (2)의 값이 변 동이 없으므로 연산 수행 가능.

Floyd의 알고리즘 II

• 출력: 최단경로의 길이가 포함된 배열 D, 그리고 다음을 만족하는 배열 P.

• 앞의 예에 대한 결과 P

최단경로의 출력

• 문제: 최단경로 상에 놓여 있는 정점을 출력.

• 위의 P를 가지고 path(5,3)을 구해 보시오.

결과: v1 v4. 즉, v5에서 v3으로 가는 최단경로 v5, v1, v4, v3 이다.

 

동적계획법에 의한 설계 절차

(단계 1) 문제의 입력에 대해서 최적(optimal)의 해답을 주는 재귀 관계식 (recursive property)을 설정

(단계 2) 상향적으로 최적의 해답을 계산

(단계 3) 상향적으로 최적의 해답을 구축

 

최적의 원칙

• 어떤 문제 사례에 대한 최적 해가 그 사례를 분할한 부분사례에 대한 최적 해를 항상 포함하고 있으면, 그 문제는 최적의 원칙(the principle of optimality)이 적용된다 라고 한다.
• 최적의 원칙이 적용되어야 지만 동적계획법을 사용할 수 있다.
• (예) 최단경로를 구하는 문제에서, vk를 vi 에서 vj 로 가는 최적 경로 상의 정 점이라고 하면, vi 에서 vk 로 가는 부분경로와 vk에서 vj 로 가는 부분경로도 반드시 최적이어야 한다. 이렇게 되면 최적의 원칙을 준수하게 되므로 동 적계획법을 사용하여 이 문제를 풀 수 있다.

• 모든 문제가 최적의 원칙이 적용되는 것은 아니다.

 

최적의 원칙이 적용되지 않는 예: 최장경로(longest path) 문제

• v1에서 v4로의 최장경로는 [v1, v3, v2, v4]가 된다.
• 그러나, 이 경로의 부분 경로인 v1에서 v3으로의 최장경로는 [v1, v3]이 아니고, [v1, v2, v3]이다.
• 따라서 최적의 원칙이 적용되지 않는다.
• 주의: 여기서는 단순경로(simple path), 즉 순환 (cycle)이 없는 경로만 고려한다. v1-v3 -v2 -v3 -v2 -v3 -v2 -v4 : 불허

• z 하나를 계산하는데 필요한 곱셈은 2회
• 행렬곱셈을 위해 총 3×2×4회의 곱셈 필요

 

연쇄 행렬곱셈(matrix-chain multiplication)

i × j 행렬과 j × k행렬을 곱하기 위해서는 i × j × k번 만큼의 곱셈이 필요.

연쇄적으로 행렬을 곱할 때, 어떤 행렬곱셈을 먼저 수행하느냐에 따라서 필요한 총 곱셈의 횟수가 달라짐.

(예)

• A1 × A2 × A3.
• A1의 크기는 10 × 100, A2의 크기 100 × 5, A3의 크기 5 × 50.
• (A1 × A2) × A3 곱셈의 총 횟수 7,500(=5,000+2,500)회
• A1 × (A2 × A3) 곱셈의 총 횟수 75,000(=25,000+50,000)회
• 따라서, 연쇄적으로 행렬을 곱할 때 곱셈의 횟수가 가장 적게 되는 최 적의 순서를 결정하는 알고리즘을 개발하는 것이 목표.

 

연쇄 행렬곱셈 무작정 알고리즘

알고리즘: 가능한 모든 순서를 모두 고려해 보고, 그 가운데에서 가장 최 소를 택한다. 시간복잡도 분석: 최소한 지수(exponential-time) 시간

증명:

• n개의 행렬(A1 , A2 ,…, An)을 곱할 수 있는 모든 순서의 가지 수를 tn이 라고 하자.
• 만약 A1이 마지막으로 곱하는 행렬이라고 하면, 행렬 A2 ,…, An을 곱 하는 데는 tn-1개의 가지수가 있을 것이다.
• An이 마지막으로 곱하는 행렬이라고 하면, 행렬 A1,…, An-1을 곱하는 데는 또한 tn-1개의 가지수가 있을 것이다.
• 그러면, tn ≥ tn-1 + tn-1 = 2tn-1이고 t2= 1이라는 사실은 쉽게 알 수 있다.
• 따라서 tn ≥ 2tn-1 ≥ 22 tn-2 ≥ … ≥ 2n-2 t2 = 2n-2 ∈ Θ(2n )

2^(n-2) ∈ Θ(2^n). tn ∈ Θ(2^n) 라는 것은 아님

 

 

연쇄 행렬곱셈 무작정 알고리즘

• 무작정 알고리즘의 모든 가능한 가지 수
• P(n) P(n) = C(n-1)

• C(n)은 n개의 노드를 갖고 있는 이진트리의 모양의 경우의 수
• 2개의 matrix를 곱하는 경우의 수- A A -1가지

• 3개의 matrix를 곱하는 경우의 수- A(A A), (A A)A, -2가지

• 4개의 matrix를 곱하는 경우의 수 - A(A(A A)), (AA)(AA), A((A A)A), ((AA)A)A, (A(AA))A -5가지

• 5개의 matrix를 곱하는 경우의 수                                                                                                    A(A-A-A-A) →5가지                                                                                                                      (A-A-A-A)A →5가지                                                                                                                      (AA)(A-A-A) →2가지                                                                                                                      (A-A-A)AA → 2가지 총 14가지.

최적의 원칙 적용 여부

• n개의 행렬을 곱하는 최적의 순서는 n개 행렬의 부분집합을 곱 하는 최적의 순서를 포함
• Ex) 6 개의 행렬을 곱하는 최적의 순서가 A1((((A2A3)A4)A5)A6)이라면 A2에서 A4까지 곱하는 최적의 순 서는 반드시 (A2A3)A4가 됨

• z 하나를 계산하는데 필요한 곱셈은 2회
• 행렬곱셈을 위해 총 3×2×4회의 곱셈 필요

 

연쇄 행렬곱셈 동적계획식 설계전략

• Ak의 크기는 dk-1 × dk : dk-1 : 행(row)의 수, dk: 열(column)의 수
• A1의 행의 수는 d0.

재귀관계식의 적용 예

최적 순서의 구축

• 최적 순서를 얻기 위해서는 M[i][j]를 계산할 때 최소값을 주는 k값을 P[i][j] 에 기억한다.
• 예: P[2][5] = 4인 경우의 최적 순서는 ((A2 A3 )A4) A5이다. 구축한 P는 다음 과 같다.

따라서, 최적 분해는 (A1((((A2 A3) A4) A5) A6)).

 

최소곱셈알고리즘

문제: n개의 행렬을 곱하는데 필요한 기본적인 곱셈의 횟수의 최소치를 결 정하고, 그 최소치를 구하는 순서를 결정하라.

입력: 행렬의 개수 n, 배열 d[i-1] × d[i]는 i번째 행렬의 규모를 나타낸다.

출력:

• 기본적인 곱셈의 횟수의 최소치를 나타내는 minmult;
• 최적의 순서를 구할 수 있는 배열 P, P 는 1…n-1 by 1..n. 여기서 P[i][j]는 행렬 i부터 j까지가 최적의 순서로 갈라지는 기점을 나타낸다.

(1,3)을 계산할 때: 64=min{0+24+5×2×4, 30+0+5×3×4}

 

최소곱셈 알고리즘의 모든 경우분석

단위연산: 각 k값에 대하여 실행된 명령문(instruction), 여기서 최소값인 지 를 알아보는 비교문도 포함한다.

입력크기: 곱할 행렬의 개수 n

분석: j = i + diagonal 이므로,

• k-루프를 수행하는 횟수 = ( j −1) − i +1 = i + diagonal −1− i +1 = diagonal
• for-i 루프를 수행하는 횟수 = n – diagonal
• 따라서

 

최적의 해를 주는 순서의 출력

• 문제: n개의 행렬을 곱하는 최적의 순서를 출력하시오.
• 입력: n과 P
• 출력: 최적의 순서

• order(1,6)은 (A1((((A2A3)A4)A5)A6)) 을 출력
• T(n) ∈ Θ(n).

다른 알고리즘

• Yao(1982) - Θ(n^2)
• Hu and Shing(1982, 1984) - Θ(n lg n)