 Dynamic Programming (동적 프로그래밍)

Presentation on theme: " Dynamic Programming (동적 프로그래밍)"— Presentation transcript:

1  Dynamic Programming (동적 프로그래밍)
알고리즘(Algorithm)  Dynamic Programming (동적 프로그래밍) 강원대학교 컴퓨터과학전공 문양세

2 Dynamic Programming 개요 (1/2)
Divide & Conquer 기법은 하향식 접근법(top-down approach)으로, 나누어진 부분들 사이에 서로 상관관계가 없는 문제를 해결하는데 적합하다. 피보나찌 알고리즘 경우 나누어진 부분들이 서로 연관이 있다.  f(5)를 계산하기 위해 f(3)를 세 번 사용? 즉, 분할정복식 방법을 적용하여 알고리즘을 설계하게 되면 같은 항을 한 번 이상 계산하는 결과를 초래하게 되므로 효율적 이지 않다. 따라서, 이 경우에는 Divide & Conquer 기법은 적합하지 않다.

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

4 이항계수(Binomial Coefficient) – 정의
Dynamic Programming 이항계수 구하는 공식 The binomial coefficient is the number of ways of picking k unordered outcomes from n possibilities, also known as a combination nCk. 계산량이 많은 n!이나 k!을 계산하지 않고 이항계수를 구하기 위해서 통상 다음 수식을 사용한다.

5 이항계수 – Divide & Conquer 알고리즘
Dynamic Programming 문제: 이항계수를 계산한다. 입력: 음수가 아닌 정수 n과 k, 여기서 k  n 출력: 이항계수 결과 값 알고리즘: int bin(int n, int k) { if (k == 0 || n == k) return 1; else return (bin(n-1,k-1) + bin(n-1,k)); }

6 이항계수 – Divide & Conquer 시간복잡도 (1/3)
Dynamic Programming 분할정복 알고리즘은 작성하기는 간단하지만, 효율적이지 않다. Why? 알고리즘을 재귀 호출(recursive call)할 때 동일한(identical) 계산을 반복해서 수행하기 때문이다. 예를 들면, bin(n-1,k-1)과 bin(n-1,k)는 둘 다 bin(n-2,k-1)의 결과가 필요한데, 따로 중복하여 계산된다. 을 구하기 위해서, Divide & Conquer 알고리즘이 계산하는 항(term)의 개수는 다음과 같다. ( 다음 페이지 증명) 이는 factorial 복잡도로서, 실제 알고리즘으로 사용할 수 없다.

7 이항계수 – Divide & Conquer 시간복잡도 (2/3)
Dynamic Programming 증명: (n에 대한 수학적귀납법으로 증명) Induction Basis: 항의 개수 n이 1일 때, 이 됨을 보이면 된다 는 k = 0이나 1 일 때, 1이므로 항의 개수는 항상 1이다. Induction Hypothesis: 을 계산하기 위한 항의 개수는 이라 가정한다. Induction Step: 을 계산하기 위한 항의 개수가 임을 보이면 된다. 알고리즘에 의해서 이므로, 를 계산하기 위한 항의 총 개수는 을 계산하기 위한 총 개수와 를 계산하기 위한 항의 총 개수에, 이 둘을 더하기 위한 항 하나를 더한 수가 된다.

8 이항계수 – Divide & Conquer 시간복잡도 (3/3)
Dynamic Programming (증명 계속) 그런데, 을 계산하기 위한 항의 개수는 가정에 의해서 이고, 를 계산하기 위한 항의 개수는 가정에 의해서 이다. 따라서 항의 총 개수는 다음과 같이 로 계산된다.

9 재귀 관계식(recursive property)을 정립
이항계수 – Dynamic Programming 설계 (1/2) Dynamic Programming 재귀 관계식(recursive property)을 정립 2차원 배열 B를 만들고, 각 B[i][j]에는 값을 저장하도록 한다. 그러면, 그 값은 다음과 같은 관계식으로 계산할 수 있다.

10 상향식 접근법을 적용 이항계수 – Dynamic Programming 설계 (2/2)
를 구하기 위해서, 다음과 같이 B[0][0]부터 시작하여 위에서 아래로 재귀 관계식을 적용하여 배열을 채워 나가면 된다. 결국, 구하려는 값은 B[n][k]에 저장된다. i  j이므로 대각선 포함 아래쪽만 값을 구하면 된다.

11 이항계수 – Dynamic Programming 알고리즘
문제: 이항계수를 계산한다. 입력: 음수가 아닌 정수 n과 k, 여기서 k  n 출력: 이항계수 결과 값 알고리즘: int bin2(int n, int k) { index i, j; int B[0..n][0..k]; for(i=0; i <= n; i++) for(j=0; j <= minimum(i,k); j++) if (j==0 || j==i) B[i][j] = 1; else B[i][j] = B[i-1][j-1] + B[i-1][j]; return B[n][k]; }

12 이항계수 – Dynamic Programming 시간복잡도
단위연산: for-j 루프 안의 문장 입력의 크기: n, k i = 0일 때 j-루프 수행 횟수 : 1 i = 1일 때 j-루프 수행 횟수 : 2 i = 2일 때 j-루프 수행 횟수 : 3 ……………….. i = k-1일 때 j-루프 수행 횟수 : k i = k일 때 j-루프 수행 횟수 : k + 1 i = k+1일 때 j-루프 수행 횟수 : k + 1 i = n일 때 j-루프 수행 횟수 : k + 1 따라서, 총 횟수는 다음과 같이 계산된다.

13 이항계수 – D&C vs. DP Dynamic Programming 시간복잡도에 있어서 큰 차이를 보이며, DP가 D&C에 비해 훨씬 우수한 알고리즘을 알 수 있다. 공간복잡도 측면에서는 언뜻 보기에 배열을 사용하는 DP가 D&C보다 더 복잡한 것으로 보인다.  정말 그럴까? DP의 공간복잡도는 O(n2)이다. 이를 O(n)으로 낮출 수 있는가?  한 행의 계산이 끝나면, 그 이전에 계산한 값은 필요하지 않다.  이 성질을 사용하면 가능하다.  알고리즘을 변경해 보세요.

14 그래프 용어 (Shortest Path Problem 이전에…)
Dynamic Programming 정점, 노드(vertex, node), 이음선, 에지(edge, arc) 방향 그래프(directed graph) 가중치(weight), 가중치 (포함) 그래프(weighted graph) 경로(path): 노드와 노드를 잇는 일련의 노드들 단순경로(simple path): 같은 정점을 두 번 지나지 않음 순환(cycle): 한 정점에서 다시 그 정점으로 돌아오는 경로 순환 그래프(cyclic graph) vs 비순환 그래프(acyclic graph) 경로의 길이(length) 가중치 그래프: 경로상에 있는 가중치의 합 일반 그래프: 에지의 개수

15 가중치 포함 방향 그래프 예제 Dynamic Programming 1 v1 v2 3 9 5 v5 1 2 3 3 2 v4 v3 4

16 최단경로 문제(Shortest Path Problem)
Dynamic Programming 보기 : 한 도시에서 다른 도시로 직항로가 없는 경우 가장 빨리 갈 수 있는 항로를 찾는 문제 문제: 가중치 포함, 방향성 그래프에서 최단경로 찾기 최단경로 찾기 문제는 최적화 문제에 속한다. 최적화 문제(optimization problem)란? 주어진 문제에 대하여 하나 이상의 많은 해답(candidate solutions)이 존재할 때, 이 가운데에서 가장 최적인 해답(optimal solution)을 찾아야 하는 문제

17 무작정 알고리즘(brute-force algorithm)
최단경로 찾기 – 무작정 알고리즘 (1/2) Dynamic Programming 무작정 알고리즘(brute-force algorithm) 한 노드에서 다른 노드로의 모든 가능한 경로의 길이를 구한다. 그들 경로 중에서 최소길이를 찾는다.

18 최단경로 찾기 – 무작정 알고리즘 (2/2) 분석:
Dynamic Programming 분석: 그래프가 n개의 노드를 가지고 있고, 모든 노드들 사이에 이음선이 존재한다고 가정하자. 그러면 한 노드 vi에서 어떤 정점 vj로 가는 경로들을 다 모아 보면, 그 경로들 중에서 나머지 모든 정점을 한번씩 은 꼭 거쳐서 가는 경로들도 포함되어 있는데, 그 경로들의 수 만 우선 계산해 보자. vi에서 출발하여 처음 도착할 수 있는 정점의 가지 수는 n-2개(vj 제외)이고, 그 중 하나를 선택하면, 그 다음에 도착할 수 있는 정점의 가지 수는 n-3개 이고, 이렇게 계속 계산해 보면, 총 경로의 개수는 (n-2)(n-3)…1 = (n-2)!이 된다. 이 경로의 개수 만 보아도 지수보다 훨씬 크므로, 이 알고리즘은 절대적으로 비효율적이다!

19 DP 기반 최단경로 – 자료 구조 (1/2) 그래프의 인접행렬(adjacent matrix)식 표현: W
Dynamic Programming 그래프의 인접행렬(adjacent matrix)식 표현: W 그래프에서 최단경로 길이의 표현: 의 정점들만을 통해서 vi에서 vj로 가는 최단경로의 길이

20 DP 기반 최단경로 – 자료 구조 (2/2) Dynamic Programming 보기: W: 그림 3.2에 있는 그래프의 인접행렬식 표현 D: 각 정점들 사이의 최단 거리 여기서, 0  k  5 일 때, D(k)[2][5]를 구해보자  p. 97의 예제 3.2 D(0) = W이고, D(n) = D임은 분명하다. 따라서 D를 구하기 위해서는 D(0)를 가지고 D(n)을 구할 수 있는 방법을 고안해 내야 한다.

21 DP 기반 최단경로 – 설계 Dynamic Programming 1. D(k-1)을 가지고 D(k)를 계산하는 재귀 관계식(recursive property)을 정립 경우 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] = = 7 보기: D(2)[5][4] 2. 상향식으로 k = 1부터 n까지 다음과 같이 상기 과정을 반복하여 해를 구한다. D(0), D(1),……., D(n)

22 DP 기반 최단경로 – Floyd 알고리즘 1 (1/2)
Dynamic Programming 문제: 가중치 포함 그래프의 각 정점에서 다른 모든 정점까지의 최단거리를 계산하라. 입력: 가중치 포함 방향성 그래프 W, 그래프에서의 정점의 수 n 출력: 최단거리의 길이가 포함된 배열 D

23 DP 기반 최단경로 – Floyd 알고리즘 1 (2/2)
Dynamic Programming 알고리즘 모든 경우를 고려한 분석: 단위연산: for-j 루프안의 지정문 입력크기: 그래프에서의 정점의 수 n void floyd(int n, const number W[][], number D[][]) { int i, j, k; D = W; for(k=1; k <= n; k++) for(i=1; i <= n; i++) for(j=1; j <= n; j++) D[i][j] = minimum(D[i][j], D[i][k]+D[k][j]); }

24 DP 기반 최단경로 – Floyd 알고리즘 2 (1/4)
Dynamic Programming 문제: 가중치 포함 그래프의 각 정점에서 다른 모든 정점까지의 최단거리를 계산하고, 각각의 최단경로를 구하라. 입력: 가중치 포함 방향성 그래프 W, 그래프에서의 정점의 수 n 출력: 최단경로의 길이가 포함된 배열 D, 그리고 다음을 만족하는 배열 P vi에서 vj 까지 가는 최단경로의 중간에 놓여 있는 정점이 최소한 하나는 있는 경우  그 놓여 있는 정점 중에서 가장 큰 인덱스 최단경로의 중간에 놓여 있는 정점이 없는 경우  0

25 DP 기반 최단경로 – Floyd 알고리즘 2 (2/4)
Dynamic Programming 알고리즘 void floyd2(int n, const number W[][], number D[][], index P[][]) { index i, j, k; for(i=1; i <= n; i++) for(j=1; j <= n; j++) P[i][j] = 0; D = W; for(k=1; k<= n; k++) for(j=1; j<=n; j++) if (D[i][k] + D[k][j] < D[i][j]) { P[i][j] = k; D[i][j] = D[i][k] + D[k][j]; } vi에서 vj로 가는데 vk를 지난다는 정보를 저장

26 DP 기반 최단경로 – Floyd 알고리즘 2 (3/4)
Dynamic Programming 그림 3-2의 예를 가지고 (D와) P를 구해 보시오.

27 DP 기반 최단경로 – Floyd 알고리즘 2 (4/4)
Dynamic Programming 최단경로 출력 알고리즘 void path(index q,r) { if (P[q][r] != 0) { path(q,P[q][r]); cout << “ v” << P[q][r]; path(P[q][r],r); } 앞서의 P로 path(5,3)을 출력하면 다음과 같다. path(5,3) = 4 path(5,4) = 1 path(5,1) = 0 v1 path(1,4) = 0 v4 path(4,3) = 0 결과: v1 v4. (즉, v5에서 v3으로 가는 최단경로는 v5, v1, v4, v3,이다.) 1

28 Dynamic Programming에 대한 설계 절차
문제의 입력에 대해서 최적(optimal)의 해답을 주는 재귀 관계식(recursive property)을 설정 상향적으로 최적의 해답을 계산 (D, P 계산) 상향적으로 최적의 해답을 구축 (경로 출력)

29 최적의 원칙 (The Principle of Optimality)
Dynamic Programming 어떤 문제의 입력에 대한 최적 해가 그 입력을 나누어 쪼갠 여러 부분에 대한 최적 해를 항상 포함하고 있으면, 그 문제는 최적의 원칙이 적용된다 라고 한다. 보기: 최단경로를 구하는 문제에서, vk를 vi에서 vj로 가는 최적 경로 상의 정점이라고 하면, vi에서 vk 로 가는 부분경로와 vk에서 vj로 가는 부분경로도 반드시 최적이어야 한다. 이렇게 되면 최적의 원칙을 준수하게 되므로 Dynamic Programming을 사용하여 이 문제를 풀 수 있다.

30 최적의 원칙이 적용되지 않는 예제 최장경로(Longest Path) 문제 v1 v2 v3 v4
Dynamic Programming 최장경로(Longest Path) 문제 v1에서 v4로의 최장경로는 [v1, v3, v2, v4]가 된다. 그러나, 이 경로의 부분 경로인 v1에서 v3으로의 최장경로는 [v1, v3]이 아니고, [v1, v2, v3]이다. 따라서 최적의 원칙이 적용되지 않는다. 주의: 여기서는 단순경로(simple path), 즉 순환(cycle)이 없는 경로만 고려한다. v1 1 1 3 v2 v3 2 4 v4

31 연쇄행렬곱셈 (Matrix-Chain Multiplication) (1/2)
Dynamic Programming i  j 행렬과 j  k행렬을 곱하기 위해서는 일반적으로 i  j  k번 만큼의 기본적인 곱셈이 필요하다. (교재 pp ) 연쇄적으로 행렬을 곱할 때, 어떤 행렬곱셈을 먼저 수행하느냐에 따라서 필요한 기본적인 곱셈의 횟수가 달라지게 된다. 예를 들어서, 다음 연쇄행렬곱셈을 생각해 보자: A1  A2  A3 A1의 크기는 10  100이고, A2의 크기는 100  5이고, A3의 크기는 5  50라고 하자. A1  A2를 먼저 계산한다면, 기본적인 곱셈의 총 횟수는 7,500회 A2  A3를 먼저 계산한다면, 기본적인 곱셈의 총 횟수는 75,000회

32 연쇄행렬곱셈 (Matrix-Chain Multiplication) (2/2)
Dynamic Programming 또 다른 예제: 교재 p. 105  연쇄적으로 행렬을 곱할 때 기본적인 곱셈의 횟수가 가장 적게 되는 최적의 순서를 결정하는 알고리즘 개발이 목표이다.

33 연쇄행렬곱셈 – 무작정 알고리즘 알고리즘: 가능한 모든 순서를 모두 고려해 보고, 그 가운데에서 가장 최소를 택한다.
Dynamic Programming 알고리즘: 가능한 모든 순서를 모두 고려해 보고, 그 가운데에서 가장 최소를 택한다. 시간복잡도 분석: 최소한 지수(exponential-time) 시간 증명: n개의 행렬(A1 , A2 ,…, An)을 곱할 수 있는 모든 순서의 가지 수를 tn이라고 하자. 만약 A1이 마지막으로 곱하는 행렬이라고 하면, 행렬 A2 ,…, An을 곱하는 데는 tn-1개의 가지수가 있을 것이다. An이 마지막으로 곱하는 행렬이라고 하면, 행렬 A1,…, An-1을 곱하는 데는 또한 tn-1개의 가지수가 있을 것이다. 그러면, tn  tn-1 + tn-1 = 2 tn-1이고, t2= 1이라는 사실은 쉽게 알 수 있다. 따라서 tn  2tn-1  22tn-2  …  2n-2t2 = 2n-2 = (2n)이다.

34 DP 기반 연쇄행렬곱셈 – 설계 (1/2) Dynamic Programming dk를 행렬 Ak의 열(column)의 수라고 하자. 그러면 자연히 Ak의 행(row)의 수는 dk-1가 된다.

35 DP 기반 연쇄행렬곱셈 – 설계 (2/2) Dynamic Programming A1의 행의 수는 d0라고 하자. 그러면, 다음과 같이 재귀 관계식을 구축할 수 있다. M[i][j] = i < j일 때 Ai부터 Aj까지의 행렬을 곱하는데 필요한 곱셈의 최소 횟수 (1  i  j  n) k = i, i+1, ..., j-2, j-1

36 DP 기반 연쇄행렬곱셈 – 재귀식 적용 예 Dynamic Programming

37 DP 기반 연쇄행렬곱셈 – 최적 순서의 구축 Dynamic Programming 최적 순서를 얻기 위해서는 M[i][j]를 계산할 때 최소값을 주는 k값을 P[i][j]에 기억한다. 예: P[2][5] = 4인 경우의 최적 순서는 (A2 A3 A4)A5이다. 구축한 P는 다음과 같다. 따라서, 최적 분해는 (A1((((A2 A3) A4) A5) A6))이다.

38 DP 기반 연쇄행렬곱셈 – 알고리즘 (1/2) Dynamic Programming 문제: n개의 행렬을 곱하는데 필요한 기본적인 곱셈의 횟수의 최소치를 결정하고, 그 최소치를 구하는 순서를 결정하라. 입력: 행렬의 수 n, 배열 d[1..n] (d[i-1]  d[i]는 i번째 행렬의 규모를 나타낸다.) 출력: 기본적인 곱셈의 횟수의 최소치를 나타내는 minmult; 최적의 순서를 얻을 수 있는 배열 P (여기서 P[i][j]는 행렬 i부터 j까지가 최적 순서로 갈라지는 기점을 나타낸다.)

39 DP 기반 연쇄행렬곱셈 – 알고리즘 (2/2) 알고리즘
Dynamic Programming 알고리즘 int minmult(int n, const int d[], index P[][]) { index i, j, k, diagonal; int M[1..n, 1..n]; for(i=1; i <= n; i++) M[i][j] = 0; for(diagonal = 1; diagonal <= n-1; diagonal++) for(i=1; i <= n-diagonal; i++) { j = i + diagonal; M[i][j] = minimum (M[i][k]+M[k+1][j]+d[i-1]*d[k]*d[j]); ikj-1 P[i][j] = 최소치를 주는 k의 값 } return M[1][n];

40 DP 기반 연쇄행렬곱셈 – 알고리즘 분석 Dynamic Programming 단위연산: 각 k값에 대하여 실행된 명령문(instruction), 여기서 최소값인 지를 알아보는 비교문도 포함한다. 입력크기: 곱할 행렬의 수 n 분석: j = i + diagonal이므로, k-루프를 수행하는 횟수 = for-i-루프를 수행하는 횟수 = n – diagonal diagonal의 범위는 1 ~ (n-1)이므로, 모든 경우 시간 복잡도는 다음과 같다.

41 DP 기반 연쇄행렬곱셈 – 최적 해의 출력 (1/2)
Dynamic Programming 문제: n개의 행렬을 곱하는 최적의 순서를 출력하시오. 입력: n과 앞서 구한 2차원 배열 P 출력: 최적의 순서 알고리즘: int minmult(int n, const int d[], index P[][]) void order(index i, index j) { if (i == j) cout << “A” << i; else { k = P[i][j]; cout << “(”; order(i,k); order(k+1,j); cout << “)”; }

42 DP 기반 연쇄행렬곱셈 – 최적 해의 출력 (2/2)
Dynamic Programming order(i,j)의 의미: Ai ... Aj 의 계산을 수행하는데 기본적인 곱셈의 수가 가장 적게 드는 순서대로 괄호를 쳐서 출력하시오. 복잡도 분석: T(n)  (n)  Why?

43 Hu and Shing(1982, 1984)  (n lg n)
DP 기반 연쇄행렬곱셈 – 개선된 솔루션 Dynamic Programming Yao(1982)  (n2) Hu and Shing(1982, 1984)  (n lg n)

44 교재의 나머지 부분 ( 자세한 내용 생략) Dynamic Programming 최적 이진검색 트리: 주어진 키 값에 대해서 검색을 최소화하는(가장 균형 잡힌) 이진트리를 구축하는 방법 교재의 알고리즘(Gilbert & Moore 1959)  (n3) Yao(1982)  (n2) 외판원 문제(Traveling Salesman Problem: TSP): 모든 도시를 방문하되 출장 시간을 최소화하는 문제 무작정 알고리즘  (n!) 교재의 알고리즘  (n2n) 최악의 경우 시간복잡도가 지수보다 좋은 TSP 알고리즘을 찾은 사람은 아무도 없다. 또한, 그런 알고리즘이 불가능하다고 증명한 사람도 없다. 56 32 51 62 115 73 108 49 89 94