Ch.03 Dynamic Programming (동적 프로그래밍 or 동적 계획법)

Presentation on theme: "Ch.03 Dynamic Programming (동적 프로그래밍 or 동적 계획법)"— Presentation transcript:

1 Ch.03 Dynamic Programming (동적 프로그래밍 or 동적 계획법)
[CPA340] Algorithms and Practice Youn-Hee Han

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

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

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

5 Dynamic Programming 개요 (4/5)
문제를 잘 분석하여 재귀적 속성(Recursive Property)을 정립한다. (교재: 재귀적 속성  재귀 관계식) 잘게 쪼개어진 작은 문제들부터 먼저 해결하는 상향식 방법으로 전체 문제를 해결한다.

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

7 이항계수(Binomial Coefficient) – 정의

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

9 이항계수 – 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)); }

10 이항계수 – 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 복잡도로서, 실제 알고리즘으로 사용하기에는 턱없이 복잡도가 높다.

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

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

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

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

15 이항계수 – 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]; }

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

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

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

19 그래프 용어 (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

20 그래프 용어 (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.

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

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

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

24 최단경로 찾기 – 무작정 알고리즘 (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

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