알고리즘 12 동적계획법

동적계획법
- 1. 문제를 부분 문제로 나눈다 
- 2. 가장 작은 부분 문제부터 해를 구한다 
- 3. 테이블에 부분 해를 저장한다 
- 4. 부분해를 이용하여 점차 상위 부분 최적해를 구한다 

-> 일반적으로 사람이 수계산하는 피보나치 수열 푸는 방법이 동적계획법과 같다 

LCS 알고리즘 ; Longest Common Subsequence ; 최장 공통 부분 수열 
- 부분수열이란 ? 수열의 일부 요소를 제거한 것
- 최장공통부분수열 ? 두 수열의 부분 수열 중 제일 긴 것 

Xi = <x1,x2,...xi>/ Yj = <y1,y2,...yj>의 문자열이 있다고 할 때, 
LCS_LENGTH(Xi,Yi) =
1) 0  :  i =0 or j =0
2) LCS_LENGTH(Xi-1,Yi-1) + 1  : xi = yi
3) MAX(LCS_LENGTH(Xi-1,Yi),LCS_LENGTH(Xi,Yi-1)) : i,j>=0 xi !=yi

최적부분구조로 되어있으므로 동적계획법을 사용할 수 있다

 

 

Algorithm/DynamicPrgoramming at main · Sukmin-LanternK/Algorithm