동적 계획법 // (Dynamic Planning, Dynamic programming, LCS)
동적 계획법 : 동적으로 변화하는 결정을 만드는 방법
<분할 정복과 동적 계획법의 차이>
1)분할 정복은 문제를 위에서부터 아래로 쪼개지만(Top-Down),
동적 계획법은 제일 작은 부분 문제부터 상위에 있는 문제로 풀어 올라간다(Bottom Up)
2)분할 정복 기법으로 쪼갠 각 단계에 있는 부분 문제들은 그 이전 단계에 있는 문제들의 답에 의존한다.
동적 계획법은 분할 정복과 달리 한번 푼 적이 있는 부분 문제의 답은 다시 푸는일이 없도록 테이블 등에 저장해 놓는다.
동적 프로그래밍으로 알고리즘을 설계할 때 부분 문제의 답을 저장해 놓는 테이블을 빼놓으면 안된다.
이 테이블이 없으면 부분 문제들의 답을 수없이 반복해서 다시 구하는 일이 생길 수도 있기 때문이다.
<동적 게획법으로 설계된 알고리즘의 동작 방식>
1) 문제를 부분 문제로 나눈다.
2) 가장 작은 부분 문제부터 해를 구한 뒤 테이블에 저장한다.
3) 테이블에 저장되어 있는 부분 문제의 해를 이용하여 점차적으로 상위 부분 문제의 최적해를 구한다.
<동적 계획법으로 풀 수 있는 문제>
최적 부분 구조(Optimal Substructure)를 갖추고 있다는 전제가 필요
최적 부분 구조 : 전체문제의 최적해가 부분 문제의 최적해로부터 만들어지는 구조
ex) 5개의 작은 문제로 쪼갤 수 있는 어떤 문제가 있다고 하면 쪼개진 문제의 해 5개를 모두 얻어야 이 문제의 해를 구할 수 있다면 이 문제는 최적 부분 구조를 갖추었다고 할 수 있다.
- 피보나치 수 구하기
- 최장 공통 부분 순서
- 피보나치 수 구하기
피보나치 수는 다음의 점화식으로 정의할 수 있다.
Fn = 0 (n=0)
Fn = 1 (n=1)
Fn = F(n-1) + F(n-2) (n>1)
다음의 점화식의 수행시간은 O(2^n)으로 굉장히 크다.
<동적 계획법을 사용하는 경우>
O(2^n) -> O(n)
먼저 이 문제가 최적 부분 구조로 이루어져 있는지 확인해야한다.
-> 피보나치 수는 부분 문제의 답으로부터 본 문제의 답을 얻을 수 있으므로 최적 부분 구조이다.
1) 문제를 부분 문제로 나눈다.
2) 가장 작은 부분 문제로부터 해를 구한 뒤 테이블에 저장한다.
3) 테이블에 저장되어 있는 부분 문제의 해를 이용하여 점차적으로 상위 부분 문제의 최적해를 구한다.
F(n) = F(n-1) + F(n-2)
F(n-1) = F(n-2) + F(n-3)
F(2) = F(1) + F(0)
-> F(n)은 F(n-1) , F(n-2) , F(n-3) , ... , F(1) , F(0) 의 부분집합으로 나뉜다.
부분 문제로 나누는 일을 끝냈으면 가장 작은 부분 문제부터 해를 구해나가야한다.
물론 그 결과는 테이블에 저장한다.
| 테이블 인덱스 | 저장되어 있는 값 |
| [0] | 0 |
| [1] | 1 |
| [2] | 1 |
| [3] | 2 |
| [4] | 3 |
| [5] | 5 |
| [6] | 8 |
| ... | ... |
| [n] | F(n) |
F(0)과 F(1)은 테이블 값을 사용
F(2)부터 미리 테이블에 저장되어 있는 값을 이요하여 차근차근 테이블을 완성한다.
F(n)을 구할 떄까지 테이블의 값을 참조해서 계산을 반복한다.
But, 분할 정복 기법을 사용해 피보나치 수를 풀 경우 O(log 2 n)으로 O(n)보다 빠르다.
- 최장 공통 부분 순서 (LCS : Longest Common Subsequence)
공통 부분 순서 : 두 순서 사이에 공통적으로 존재하는 부분 순서
최장 공통 부분 순서 : 여러 갱의 공통 부분 순서 중에 가장 긴 것
주로 두 데이터를 비교할때 아주 유용하다.
<LCS 알고리즘>
문제를 풀기 전 이 문제가 최적 부분 구조로 이루어져 있는지를 확인해야 된다.
두 문자열 X(i) = <x(1), x(2), x(3), ... , x(i)>, Y(i) = <y(1), y(2), y(3), ... , y(i)>인 두 문자열이 있다.
이 두 문자열을 매개 변수로 받아 이들 사이에서 나올 수 있는 LCS의 길이를 구하는 함수를 LCS_LENGTH()라고 한다.
먼저, i나 j 둘 중 하나가 0이라면 LCS_LENGTH(X(i), Y(j))의 결과는 0이 된다.
i나 j가 0이라는 것은 두 문자열 중 하나의 길이가 0이라는 것을 의미하고, 둘 중 하나의 길이가 0이라면 공통 부분 순서라는 것은 존재하지 않는다.
x(i), y(j)가 같다면, 즉 X(i), Y(j)의 마지막 요소가 같다면 LCS_LENGTH(X(i), Y(j))는 LCS_LENGTH(X(i-1), Y(j-1))+1을 반환한다. 두 문자열의 동일한 마지막 요소는 당연한 LCS에 포함되므로 상수 1로 대체할 수 있기 때문이다.
그리고 마지막 요소를 뺀 두 문자열끼리의 LCS의 길이를 구하여 상수 1과 더하면 원래 구하고자 했던 LCS의 길이를 얻을 수 있다.
따라서 이 경우에는 다음과 가은 점화식이 성립한다.
LCS_LENGTH(X(i), Y(j)) = LCS_LENGTH(X(i-1), Y(j-1))+1
두 문자열의 길이가 어느 한쪽도 0이 아니고 마지막 요소도 서로 다른 경우에는 LCS_LENGTH(X(i), Y(j))와 LCS_LENGTH(X(i-1), Y(j-1)) 중에서 큰 쪽이 LCS_LENGTH(X(i), Y(j))의 해이다.
두 문자열의 마지막 요소를 각각 x(i), y(j)라고 하면 이 두 요소끼리는 같지 않지만 x(i)하고 y(i-1)은 같을 수 있다.
또는, x(i-1)하고 y(j)도 같을 수 있다.
따라서 이 경우에는LCS_LENGTH(X(i-1), Y(j))와 LCS_LENGTH(X(i), Y(j-1)) 중에서 큰 쪽이 LCS_LENGTH(X(i), Y(j))의 해가 된다.
위 세 가지 경우를 정리하면 점화식을 만들면 다음과 같다.
LCS_LENGTH(X(i), Y(j)) = 0 (i=0 or j=0)
= LCS_LENGTH(X(i-1), Y(j-1)) (x(i) = y(i))
= MAX( LCS_LENGTH(X(i-1), Y(j)), LCS_LENGTH(X(i), Y(j-1)) ) ( i,j>= 0 and x(i) != y(i) )
즉, 이 문제는 최적 부분 구조로 되어 있어서 동적 계획법으로 해를 구하는 것이 가능하다.
위 점화식은 아래와 같이 정의도 가능하다.
이 점화식은 i x j 의 테이블이 있다고 했을 때, TABLE[i, j]는 LCS의 길이이며 TABLE의 각 요소는 TABLE[i, j]의 부분 문제들의 답을 담고 있다.
TABLE[i, j] = 0
= TABLE[i-1, j-1]+1
= MAX(TABLE[i-1, j],TABLE[i, j-1] ( i,j>= 0 and x(i) != y(i) )
위 점화식에서 나오는 i=0, j=0은 C 언어에서으 ㅣ배열 인덱스처럼 첫 번째 요소를 가리키는 것이 아니다.
i=0. j=0은 아무 것도 없음을 나타낸다.
문자열 X의 첫번째 요소는 i=1 , 문자열 Y의 첫번째 요소는 j=1이다.
LCS테이블의 크기는 i x j 가 아닌 (i+1) x (j+1)이다.
-> 이 테이블이 점화식의 테이블보다 행과 열이 1씩 더 긴 이유는 아무것도 없는 행 (i=0), 열(j=0)을 표현하기 위해서 이다.
O(2^(n+m)) 수행시간을 갖는다.
<동적 계획법으로 설계하는 LCS 알고리즘>
O(2^(n+m)) -> O(nm)
LCS 문제도 다음의 동적 프로그래밍 세 단계로 푼다.
1) 문제를 부분 문제로 나눈다
2) 가장 작은 부분 문제부터 해를 구한 뒤 테이블에 저장한다
3) 테이블에 저장되어 있는 부분 문제의 해를 이용하여 점차적으로 상위 부분 문제의 최적해를 구한다.
//밑에 부분 이후 추가