Ch.03 Dynamic Programming (동적 프로그래밍 or 동적 계획법) [CPA340] Algorithms and Practice Youn-Hee Han http://link.koreatech.ac.kr

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

Dynamic Programming 개요 (2/5) Dynamic programming 기법은 상향식 해결법(bottom-up approach)을 사용하여 알고리즘을 설계하는 방법이다. 이 방법은 Divide & Conquer 기법과 마찬가지로 문제를 나눈 후에 나누어진 부분들을 먼저 푼다. 그러나 이미 풀어서 답을 알고 있는 부분의 결과가 다시 필요한 경우에는 반복하여 계산하는 대신에 이미 계산된 결과를 사용한다. 반복적 (Iterative) 피보나치 알고리즘 가장 초보적인 Dynamic Programming 기법 int fib2 (int n) { index i; int[] f = new int[n+1]; f[0] = 0; if (n > 0) { f[1] = 1; for (i = 2; i <= n; i++) f[i] = f[i-1] + f[i-2]; } return f[n];

Dynamic Programming 개요 (3/5) 즉, Divide & Conquer는 위에서 시작하여 필요한 계산을 해 나가는 반면에, Dynamic programming은 밑에서 시작하여 문제를 해결하기 위하여 필요한 부분 결과를 한 번씩만 계산하고 그 결과를 차곡차곡 저장하면서 원하는 답을 찾아 나간다.  계획적이다!!! Reuse earlier results!  Memorization & Reuse!

Dynamic Programming 개요 (4/5) 문제를 잘 분석하여 재귀적 속성(Recursive Property)을 정립한다. (교재: 재귀 관계식  재귀적 속성) Recursive property for Fibonacci  f[i] = f[i-1] + f[i-2] 잘게 쪼개어진 작은 문제들부터 먼저 해결하는 상향식 방법으로 전체 문제를 해결한다. long fib2 (int n) { index i; long[] f = new long[n+1]; f[0] = 0; if (n > 0) { f[1] = 1; for (i = 2; i <= n; i++) f[i] = f[i-1] + f[i-2]; } return f[n];

Dynamic Programming 개요 (5/5) 도로 지도에서 출발점에서 목적지까지의 최단 경로의 수 A에서 B까지의 최단 경로의 수는?

이항계수(Binomial Coefficient) – 정의

이항계수(Binomial Coefficient) – 정의 파스칼의 삼각형 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 … c(0,0) c(1,0) c(1,1) c(2,0) c(2,1) c(2,2) c(3,0) c(3,1) c(3,2) c(3,3) c(4,0) c(4,1) c(4,2) c(4,3) c(4,4) Web Programming

이항계수(Binomial Coefficient) – 정의 이항계수 구하는 공식 계산량이 많은 n!이나 k!을 계산하지 않고 이항계수를 구하기 위해서 다음과 같은 재귀식을 사용할 수 있다.

이항계수 – Divide & Conquer 알고리즘 문제: 이항계수를 계산한다. 입력: 음수가 아닌 정수 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)); }

이항계수 – Divide & Conquer 시간복잡도 (1/3) 분할정복 알고리즘은 작성하기는 간단하지만, 효율적이지 않다. Why? 알고리즘을 재귀 호출(recursive call)할 때 동일한(identical) 계산을 반복해서 수행하기 때문. 또, 나누어진 부분 집합의 크기가 n에 가깝다. bin(n-1,k-1)과 bin(n-1,k)는 둘 다 bin(n-2,k-1)의 결과가 필요한데, 중복하여 계산된다. 즉, 같은 계산을 중복해서 수행 을 구하기 위해서, Divide & Conquer 알고리즘에 의한 항 (term)의 총수는 다음과 같다. ( 다음 페이지 증명) 이는 factorial 복잡도로서, 실제 알고리즘으로 사용하기에는 턱없이 복잡도가 높다.

이항계수 – Divide & Conquer 시간복잡도 (2/3) Induction Basis: n이 1일 때, 이다. Induction Hypothesis: 을 계산하기 위한 항의 총 수는 이라 가정한다. Induction Step: 을 계산하기 위한 항의 총 수가 임을 보이면 된다. 알고리즘에 의해서 이므로, 를 계산하기 위한 항의 총 개수는 을 계산하기 위한 총 개수와 를 계산하기 위한 항의 총 개수에, 이 둘을 더하기 위한 항 하나를 더한 수가 된다.

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

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

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

이항계수 – Dynamic Programming 알고리즘 j = B[4][2]   문제: 이항계수를 계산한다. 입력: 음수가 아닌 정수 n과 k, 여기서 k  n 출력: 이항계수 결과 값 알고리즘: [알고리즘 3.2] (P.93) int bin2(int n, int k){ index i, j; int[][] B = new int[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]; }

이항계수 – 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 따라서, 총 횟수는 다음과 같이 계산된다.

이항계수 – D&C vs. DP D&C 와 DP 의 공통점 둘 다 재귀적 속성을 찾아 이용한다는 점 D&C 와 DP 의 차이점 주로 Recursive Function Call 사용 DP는 작은 사례부터 시작하여 반복적으로(Iteratively) 해답을 구함  부분 사례를 한번씩만 계산 시간복잡도에 있어서 DP가 D&C에 비해 우수

[실습 5] 이항 계수 구하는 알고리즘 작성  

그래프 용어 (Shortest Path Problem 이전에…) Graph G=(V, E) is a collection of V: the set of nodes (vertices), and E: the set of lines (edges, arcs) The lines in a graph are called Undirected graphs: edge Directed graphs(방향그래프) (Digraph): arc (or directed edge) edge arc

그래프 용어 (Shortest Path Problem 이전에…) 가중치(weight), 가중치 (포함) 그래프(weighted graph) A weighted graph is a graph G=(V, E) along with a function w:ER that associates a numerical weight to each edge.

그래프 용어 (Shortest Path Problem 이전에…) 단순경로(simple path): 같은 정점을 두 번 지나지 않음. 즉, 순환이 존재하지 않음 순환(cycle): 한 정점에서 다시 그 정점으로 돌아오는 경로 순환 그래프(cyclic graph) vs 비순환 그래프(acyclic graph) 경로의 길이(length) 일반 그래프: 에지의 개수 가중치 그래프: 경로상에 있는 가중치의 합

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

최단경로 문제(Shortest Path Problem) 문제: 가중치가 있는 방향 그래프에서 임의의 두 정점간의 최단경로 찾기 최단경로: 두 정점간의 각 경로에 존재하는 가중치의 합이 가장 최소인 경로 예제: 한 도시에서 다른 도시로 직항로가 없는 경우 가장 빨리 갈 수 있는 항로를 찾는 문제 최적화 문제(optimization problem)란? 주어진 문제에 대하여 하나 이상의 많은 후보 해답(candidate solutions)이 존재할 때, 이 가운데에서 가장 최적인 해답(optimal solution)을 찾아야 하는 문제 최적해는 문제의 종류에 따라 최대값일 수도 있고 최소값일 수도 있다. 최단경로 찾기 문제는 최적화 문제에 속한다.

최단경로 찾기 – 무작정 알고리즘 (1/2) 무작정 알고리즘(brute-force algorithm) v1 v2 v5 v4 한 노드에서 다른 노드로의 모든 가능한 경로의 길이를 구한다. 그들 경로 중에서 최단경로를 찾는다. v5 v1 v4 v2 v3 3 5 1 9 2 4 E.g.) v1  v3 (1) v1  v2  v3 : the sum of weights - 4 (2) v1  v4  v3 : the sum of weights - 3  최단경로 (3) v1  v2  v4  v3 : the sum of weights - 5

최단경로 찾기 – 무작정 알고리즘 (2/2) 분석: 그래프가 n개의 노드를 가지고 있고, 모든 노드들 사이에 서로서로 이음선이 존재한다고 가정 (Complete Graph) 하자. 그래프 내의 이음선 개수 = 그러면 한 노드 vi에서 다른 노드 vj로 가는 경로의 개수는? vi에서 출발하여 처음 도착할 수 있는 정점의 수는 n-2개(vj 제외)이고, 그 중 하나를 선택하면, 그 다음에 도착할 수 있는 정점의 수는 n-3개 이고, 이렇게 계속 계산해 보면, 총 경로의 개수는 (n-2)(n-3)…1 = (n-2)!이 된다. 이 경로의 개수 만 보아도 Brute-Force 알고리즘의 시간복잡도는 Factorial 복잡도로서 지수 시간복잡도보다 훨씬 크다. 즉, Brute-Force 알고리즘은 절대적으로 비효율적이다! http://en.wikipedia.org/wiki/Complete_graph

DP 기반 최단경로 – 자료 구조 및 전략 (1/4) 주어진 그래프에 대한 W:인접행렬(adjacent matrix) 표현 W v5 v1 v4 v2 v3 3 5 1 9 2 4 W

DP 기반 최단경로 – 자료 구조 및 전략 (2/4) 주어진 그래프에 대한 최단경로의 길이를 나타내는 행렬: D 즉, 알고리즘에 의해서 생성할 목표에 해당하는 자료구조 즉, W: 주어진 그래프의 인접행렬 표현 D: 주어진 그래프의 각 정점들 사이의 최단경로의 길이 v5 v1 v4 v2 v3 3 5 1 9 2 4 D

DP 기반 최단경로 – 자료 구조 및 전략 (3/4)  

DP 기반 최단경로 – 자료 구조 및 전략 (4/4) v5 v1 v4 v2 v3 3 5 1 9 2 4 예제

DP 기반 최단경로 – 설계 (1/4)   v5 v1 v4 v2 v3 3 5 1 9 2 4

DP 기반 최단경로 – 설계 (2/4)   v5 v1 v4 v2 v3 3 5 1 9 2 4

DP 기반 최단경로 – 설계 (3/4) 1. D(k-1)을 가지고 D(k)를 계산하는 재귀적 속성(recursive property)을 정립 경우 2에 대한 그림설명 2. 상향식으로 k = 1부터 n까지 다음과 같이 상기 과정을 반복하여 해를 구한다. D(0), D(1),……., D(n) {v1, v2,…, vk-1} {v1, v2,…, vk-1}

DP 기반 최단경로 – 설계 (4/4) v5 v1 v4 v2 v3 3 5 1 9 2 4 예제 W

DP 기반 최단경로 – Floyd 알고리즘 1 (1/2) 문제: 가중치 포함 방향 그래프의 각 정점에서 다른 모든 정점까지의 최단거리를 계산하라. 입력: 가중치 포함 방향 그래프 W, 그래프에서의 정점의 수 n 출력: 최단거리의 길이가 포함된 배열 D 알고리즘 void floyd(int n, number[][] W, number[][] D){ index 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]); }

DP 기반 최단경로 – Floyd 알고리즘 1 (2/2) 모든 경우를 고려한 분석: 단위연산: for-j 루프안의 할당문 입력크기: 그래프에서의 정점의 수 n

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

DP 기반 최단경로 – Floyd 알고리즘 2 (2/4) void floyd2(int n, 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를 지난다는 정보를 저장 D[i][j] = minimum(D[i][j], D[i][k]+D[k][j]);

DP 기반 최단경로 – Floyd 알고리즘 2 (3/4) v5 v1 v4 v2 v3 3 5 1 9 2 4 예 1) v2 에서 v1 까지 가는 최단경로 P[2][1]=5, P[2][5]=4, P[2][4]=0 그러므로, v2  v4  v5  v1 예 2) v5 에서 v3 까지 가는 최단경로 P[5][3]=4, P[5][4]=1, P[5][1]=0 그러므로, v5  v1  v4  v3

DP 기반 최단경로 – Floyd 알고리즘 2 (4/4) void path(index q, r){ if (P[q][r] != 0) { path(q, P[q][r]); System.out.print(“ v“ + P[q][r]); } 최단경로 출력 알고리즘 (주의: 교재와 상이) 앞서의 행렬 P로 path(5,3)을 호출하면 다음과 같이 수행된다. path(5, 3) path(5, P[5][3]=4) path(5, P[5][4]=1) P[5][1]=0  return; v1 v4 결과: v1 v4. (즉, v5에서 v3으로 가는 최단경로는 v5, v1, v4, v3,이다.)

[실습 6] Floyd 알고리즘 작성 Floyd 알고리즘을 Java 로 코딩하기 Floyd.java 를 분석하기 “// Write Codes...” 라고 되어진 세 부분을 채워넣기 다음과 같이 출력되어야 함