5장 동적계획법 (Dynamic Programming)

7.5 두 문자열 매칭 문제 예: X = photograph, Y = tomography 두 스트링 X = x1 x2 x3…xm과 Y = y1 y2 … yn에 대하여 가장 길이가 긴 공통의 부분스트링(substring)을 구하라.. 예: X = photograph, Y = tomography X와 Y의 가장 길이가 긴 공통의 부분 스트링: ograph 부분 문제 : X의 xi와 Y의 yj에서 끝나는 가장 길이가 긴 공통의 부분 스트링을 찾아라 부분문제 최적 해의 목적함수 length[i][j] = X의 xi와 Y의 yj에서 끝나는 부분 스트링으로서 가장 길이가 긴 공통의 부분 스트링의 길이 주어진 문제의 최적해 목적함수: min {length[i][j]} 1im,1jn 부분문제 최적 해의 목적함수의 재귀적 정의: length[i][j] = length[i-1][j-1] + 1 if xi = yj otherwise 시간복잡도 O(mn) int bin(int n, int k) { if (k == 0 || n == k) return 1; else return bin(n-1, k-1) + bin(n-1, k); }

7.6 두 문자열의 유사도 (Global alignment) 두 문자열 A = a1 a2 … am과 B = b1b2…bn에 대하여 A와 B의 유사도를 구하여라.  공백을 넣어서 A와 B를 맞추는 방법(alignment)의 점수: 대응하는 모든 두 문자에 대한 점수의 총합 (대응하는 두 문자가 같을 때 점수: 1 (s1), 대응하는 두 문자가 다를 때 점수: –1 (s2), 공백과 문자가 대응할 때 점수: –1 (s3))  두 문자열 A와 B의 유사도: A와 B를 가장 잘 맞출 때의 점수 예 A = abbc , B = babb 방법 1) a b b c 방법 2) - a b b c b a b b b a b b – 점수: -2 점수: 1 int bin(int n, int k) { if (k == 0 || n == k) return 1; else return bin(n-1, k-1) + bin(n-1, k); }

부분 문제: Ai = a1a2…ai, Bj = b1b2…bj의 유사도를 구하라. 부분문제 최적 해의 목적함수: C[i][j]: Ai 와 Bj의 유사도 주어진 문제의 최적해 목적함수: C[m][n] 부분문제 최적 해의 목적함수의 재귀적 정의: C[i][j] = min C[i-1][j] - 1 (ai에 공백을 대응) C[i][ j-1] - 1 (bj에 공백을 대응) C[i-1][j-1] + x[i][j] (ai 와 bj를 대응)   여기서, x[i][j] = 1 if ai = bj -1 if ai  bj j i i 시간복잡도: O(mn)

  예 b a -1 -2 -3 -4 -5 1 2 c b a D L c D: 대각선 U:위 L:왼쪽 i  

7.7 유사한 부분문자열 찾기 (Local alignment) 두 문자열 P = p1 p2 … pm과 T = t1t2 …tn에 대하여 T의 부분문자열로서 P와 가장 유사한 것을 찾아라. 예 A = abcbcbababddcd , B = babbc int bin(int n, int k) { if (k == 0 || n == k) return 1; else return bin(n-1, k-1) + bin(n-1, k); }

t1t2….tj의 tj에서 끝나는 부분문자열로서 p1p2…pi와 가장 유사한 문자열을 찾아라 부분문제 최적 해의 목적함수 부분문제: t1t2….tj의 tj에서 끝나는 부분문자열로서 p1p2…pi와 가장 유사한 문자열을 찾아라 부분문제 최적 해의 목적함수 C[i][j] = tj에서 끝나는 부분문자열 중 p1p2…pi와 최대 유사도 주어진 문제의 최적 해 목적함수: min1im C[m][i] 부분문제 최적 해의 목적함수의 재귀적 정의: C[i][j] = min C[i-1][j] - 1 (pi에 공백을 대응) C[i][ j-1] - 1 (tj에 공백을 대응) C[i-1][j-1] + x[i][j] (pi 와 tj를 대응) 여기서, x[i][j] = 1 if pi = tj -1 if pi  tj int bin(int n, int k) { if (k == 0 || n == k) return 1; else return bin(n-1, k-1) + bin(n-1, k); } 시간복잡도: O(mn)

7.8 그래프에서 모든 두 정점 사이의 최단경로찾기 그래프 G = (V,E)에서 모든 두 정점 i, j에 대하여 i로부터 j까지 가는 최단 경로를 찾아라. 즉, n  n 행렬 D를 구하라: (정점들은 1부터 n까지 번호가 붙여져 있다고 가정) D[i][j]:정점 i에서 정점 j까지 가는 최단경로의 길이  부분 문제: 그래프에서 모든 vertex u, v에 대하여 k보다 같거나 작은 vertex들을 통하여 u로 부터 v까지 가는 최단 경로를 구하라.  부분문제 최적해의 목적함수 행렬 Ak: Ak[i][j]: k보다 같거나 작은 vertex들을 통하여 vertex i로부터 vertex j까지 가는 최단경로의 길이 주어진 문제의 최적해의 목적함수 행렬 An 부분문제 최적 해의 목적함수의 재귀적 정의: Ak에 대한 recurrence relation Ak[i][j] = min {Ak-1 [i][j], Ak-1 [i][k] + Ak-1 [k][j]} A0 : 인접 비용행렬(Adjacency Cost Matrix) int bin(int n, int k) { if (k == 0 || n == k) return 1; else return bin(n-1, k-1) + bin(n-1, k); }

7.9 그래프에서 transitive closure 찾기 그래프 G = (V,E)에서 모든 두 정점 i, j에 대하여 i로부터 j까지 가는 경로의 존재 유무를 구하라. 즉, n  n 행렬 T를 구하라: (정점들은 1부터 n까지 번호가 붙여져 있다고 가정) T[i][j] = 1, if there is a path from vertex i to vertex j = 0. otherwise  부분문제: 정점 i로부터 정점 j까지 k보다 같거나 작은 정점들을 (중간 정점들로) 지나면서 i로부터 j까지 가는 경로의 존재 유무를 구하라. 즉 n  n 행렬 Ak를 구하라. Ak[i][j] = 1, 정점 u로부터 정점 v까지 k보다 같거나 작은 정점들을 지나면서 u로부터 v까지 가는 경로가 있으면 = 0. 그렇지 않으면 A0: 인접행렬 주어진 문제의 해: An[i][j] 부분문제 해의 재귀적 정의: Ak[i][j] = Ak-1[i][j] or (Ak-1[i][k] and Ak-1[k][j] ) int bin(int n, int k) { if (k == 0 || n == k) return 1; else return bin(n-1, k-1) + bin(n-1, k); }