[문제 해결 알고리즘] 동적 계획법 ②

1. 편집 거리 문제

(1) 개요

 - 문서 편집기를 사용하는 중에하나의 스트링(문자열) S를 수정하여 다른 스트링 T로 변환시키고자 할 때, 다음과 같은 연산 활용

 - 삽입/삭제/대체

 - 편집 거리 : S를 T로 변환시키는데 필요한 최소 편집 연산 횟수

 - strong 을 stone으로 편집 시 s, t 그대로 r 삽입, o, n 그대로, g>e 대체로 2번의 편집 연산 수행

 - strong을 stone으로 편집 시 각 접두부(Prefix)에 대해서 편집 거리를 알고 있는 경우

   stro를 sto를 편집할 때의 편집거리에 대해서 미리 알고있으면,

  > 각 스트링의 나머지 부분에 대해서 즉, ng를 ne로의 편집에 대해서 편집 거리를 찾음

  > 주어진 입력에 대한 편집 거리를 구할 수 있음

(2) 방법

- s1, s2, s3, s4 > t1, t2, t3 즉 E[4,3]은 어떻게 계산 해야할까?

- 부분 문제 s1s2s3s4 > t1t2['stro'를 'st'로 편집] E[4,2]의 해를 알면,

  t3 = 'o'를 삽입하면 됨, 따라서 이 때의 편집 연산 횟수는 E[4,2] +1 임

- 부분 문제 s1s2s3 > t1t2t3 ['str'을 'sto'로 편집] E[3,3]의 해를 알면,

  s4='o'를 삭제하면 됨, E[3,3] +1임

 - 부분 문제 s1,s2,s3 > t1,t2 ['str'을 'st'로 편집]

  E[3,2]의 해를 알면, s4='o'를 t3='o'로 편집하는데 필요한 연산을 계산, 2개의 문자가 같으므로 E[3,3] = E[3,2]임

 - 일반적으로 E[i-1, j] E[i,j-1], E[i-1,j-1]의 해가 미리 계산되어있으면 E[i,j]를 계산할 수 있음

 > E[ij] = min{E[i,j-1]+1, E[i-1,j]+1, E[i-1,j-1]+a} 단, a=1 if si != ti else a=0

(3) 알고리즘

 - 입력 : 스트링 S, T (다느 S와 T의 길이는 각 m, n)

 - 출력 : S > T 변환하는 편집거리 E[m,n]

ⓐ for i = 0 to m E[i,0] = i

ⓑ for j = 0 to n E[0,j] = j

ⓒ for i = 1 to m

ⓓ fot j = 1 to n

ⓔ E[i,j] = min{ E[i,j-1]+1, E[i-1,j]+1, E[i-1,j-1]+a}

ⓕ return E[m,n]

(4) 예제

 - strong을 stone으로 바꾸는데 필요한 편집 거리

S/T	null	s	t	o	n	e
null	0	1	2	3	4	5
s	1	0	1	2	3	4
t	2	1	0	1	2	3
r	3	2	1	1	2	3
o	4	3	2	2	1	2
n	5	4	3	3	2	1
g	6	5	4	4	3	2

(5) 시간복잡도 = O(mn)

 - 총 부분문제의 수가 배열 E의 원소 수

 - 각 부분문제를 계산하기 위해 주위의 3개의 부분문제들의 해를 참조 후 최소값을 찾는 것 = x * O(1)씩 걸리는 것

2. 모든 쌍 최단 경로 문제

(1) 개요

 - 각 쌍의 점 사이의 최단 경로를 찾는 문제

 - 각 점을 시작점으로 정하여 다익스트라의 최단 경로 알고리즘을 수행하면 됨 (O(n^3))

 - 플로이드 - 워샬 알고리즘 : 모든 쌍 최단 경로를 찾는 동적 계획 알고리즘 (O(n^3))

   > 다익스트라 알고리즘을 n-1번 사용할때의 시간복잡도와 동일

  > 프로이드 알고리즘은 매우 간단하여 다익스트라 알고리즘을 사용하는 것보다 효율적

(2) 방법

- 그래프에 점 3개가 있는 경우, 점 i에서 점 j까지 최단 경로를 찾으려면, 점 i에서 점 j로 가는 직접 경로와 점 k을 경유하는 경로 중 짧은 것을 선택함

- 그래프에 점 n개가 있는 경우, 점 1부터 시작하여 점 1,2 점 1,2,3으로 하나씩 추가함, 마지막에는 점 1~n까지의 모든 점을 경유 가능한 점들로 고려하면서 모든 쌍의 최단 경로의 거리를 계산함

- 부분 문제 정의 : 점 {1,2,...,k}만을 경유 가능한 점들로 고려하여 점 i로부터 점 j까지의 모든 경로 중 가장 짧은 경로의 거리 Dji

  i에서 점 1을 경유하여 j로 가는 경로와 i에서 j로 직접 가는 경로 중에 짧은 거리

(3) 알고리즘

- 입력 : 2차원 배열 D

             D[i, j] = 선분 (i,j)의 가중치, 만일 선분 (i, j)가 존재하지 않으면 D[i, j] = 무한대, 모든 i에 대하여 D[i, j] = 0

- 출력 : 모든 쌍 최단 경로의 거리를 저장한 배열 D

ⓐ for k =1 to n

ⓑ for i = 1 to n (단, i <> k)

ⓒ for j = 1 to n (단, i <> k, j <> i)

ⓓ D[i, j] = min{D[i,k]+D[k,j], D[i,j]}

(4) 예제

 - 배열 D의 원소들이 k가 1부터 5까지 증가함에 따라서 갱신됨

구분	1	2	3	4	5
1	0	4	2	5
2		0	1		4
3	1	3	0	1	2
4	-2			0	2
5		-3	3	1	0

>> 이와 같이 배열로 표기 필요

 - 배열 D의 원소들이 k가 1부터 5까지 증가함에 따라서 갱신됨

 - k = 1일 때

구분	1	2	3	4	5
1	0	4	2	5
2		0	1		4
3	1	3	0	1	2
4	-2	2	0	0	2
5		-3	3	1	0

- k = 2일 때

구분	1	2	3	4	5
1	0	4	2	5	8
2		0	1		4
3	1	3	0	1	2
4	-2	2	0	0	2
5		-3	-2	1	0

(5) 시간복잡도 = O(n^3)

- 각 k에 대하여 모든 i, j쌍에 대해 계산되므로 총 n*n*n회 계산이 이루어짐

3. 최적성의 원리

- 어떤 문제의 최적해가 그 문제의 부분 문제들을 최적해로 구성되는 경우, 그 문제는 최적성의 원리를 만족함

- 동적 계획법은 최적성의 원리가 적용되는 문제에 대해서만 사용 가능함

- 최단 경로 문제 (vi에서 vj까지 최단경로가 vk를 포함하면 이 경로의 부분 경로인 vi에서 vk까지의 경로는 두 정점간의 최단 경로임)

  단, 최장 경로 문제는 적용되지 않음

- 그리디 방법과 동적 계획법 모두 최적화 문제를 풀 때 사용됨

- 욕심쟁이 방법 : 알고리즘은 매우 간단하고, 동적 계획법보다 효율적일 가능성이 큼, 최적회를 구할 수 있다는 방법을 증명해야 함

- 동적 계획법 : 최적성의 원리를 만족하는 문제들에 대해, 항상 최적의 해를 구할 수 있음, 일반적으로 분할 정복 방식보다 효율적임