'Dynamic Programming'에 해당되는 글 1건

  1. 2007.04.05 Dynamic programming
반응형

Dynamic programming은 어떤 상태에서의(n) 최적화된 솔류션 S(n)은 그 전의 최적화된 상태에 의해서 조합될수 있는 경우 적용이 가능하다.


예를 들어 "동전에 숫자가 1,3,5 로 적혀 있을 경우 합이 11인 최소의 동전 개수는?"에 대한 최적의 솔류션은


1. 합이 10인 솔류션 + 숫자1이 쓰여진 동전 1개

2. 합이 8인 솔류션 + 숫자3이 쓰여진 동전 1개

3. 합이 5인 솔류션 + 숫자5가 쓰여진 동전 1개

이 3가지 솔류션중 가장 동전 수가 작은 것의 동전 수가 답이다.


즉 S(11)=MAX(S(10),S(8),S(5))+1 이 된다.

일반적으로 S(n)=MAX(S(n-1),S(n-3),S(n-5))+1 이며 이를 기반하여 위의 예제를 풀어 보면

0. S(0)=0

1. S(1)=MAX(S(0))+1=1

2. S(2)=MAX(S(1))+1=2

3. S(3)=MAX(S(2),S(0))+1=1

4. S(4)=MAX(S(3),S(1))+1=2

5. S(5)=MAX(S(4),S(2),S(0))+1=1

....뭐..이런 식이다.


다른 예를 들어 보면

LCS(Longest Common String)인데 DNA분석에 있어서 가장 긴 공통 문자열을 의미하는데,

예를 들어 GATTACGTC와 GTACAAT에서 LCS는

G A T T A C G T C

G    T    A C A A T

G    T    A C    T 가 될것이다(맞나??) 이것도 잘 보면

X(m) 및 Y(n)의 문자열에 대해서

만약 X(m)==Y(n)이면 LCS(m,n)=LCS(m-1,n-1)+1이 된다.

X(m)!=Y(n)이면 LCS(m,n)= MAX(LCS(m-1,n),LCS(m,n-1))이 된다.

반응형
Posted by alias
,