[알고리즘] 동적 계획법, DP 적용(피보나치 수)

동적 계획법

• 동적계획법은 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘이다.
• 동적 계획법은 먼저 작은 부분 문제들의 해들을 구하고 이들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여, 최종적으로 원래 주어진 문제를 해결하는 알고리즘 설계 기법이다.

동적계획법 적용 요건

중복 부분문제 구조(Overlapping subproblems)
최적 부분 문제 구조(optimal substructure)

중복 부분문제 구조(Overlapping subproblems)

• DP는 큰 문제를 이루는 작은 작은 문제들을 먼저 해결하고 작은 문제들의 최적 해를 이용하여 순환적으로 큰 문제를 해결한다. // 순환적인 관계를 명시적으로 표현하기 위해서 동적 계획법에서는 일반적으로 점화식을 사용함.
• DP는 문제의 순환적인 성질 때문에 이전에 계산되어졌던 작은 문제의 해가 다른 어딘가에서 필요하게 되는데 이를 위해 DP에서는 이미 해결된 작은 문제들의 해들을 어떤 저장 공간에 저장하게 된다.
• 그리고 저장된 해들이 다시 필요할 때마다 다시 계산하지 않고 저장 공간을 참조해서 중복 계산을 피하게 된다.

최적 부분문제 구조(Optimal substructure)

동적 계획법이 최적화에 대한 어느 문제에나 적용될 수 있는 것은 아니고 최적화 원칙을 만족할 때 동적 계획법을 효율적으로 적용할 수 있다.

• 최적화의 원칙이란 어떤 문제에 대한 해가 최적일 때 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 한다는 것이다. 동적 계획법의 방법자체가 큰 문제의 최적 해를 작은 문제의 최적해들을 이용하여 구하기 때문에 만약 큰 문제의 최적해가 작은 문제들의 최적해들로 구성되지 않는다면 이 문제는 동적 계획법을 적용할 수 없다.

최적의 원칙이 적용되지 않는 예 : 최장경로(Longest Path)

DP 적용 접근 방법

1. 최적해 구조의 특성을 파악하기 : 문제를 부분 문제로 나눈다.
2. 최적해의 값을 재귀적으로 정의하기 : 부분 문제의 최적해 값에 기반하여 문제의 최적해 값을 정의한다.
3. 상향식 방법으로 최적해의 값을 계산 : 가장 작은 문제부터 해를 구하고 저장, 저장되어 있는 부분 문제의 해를 이용하여 점차적으로 상위 부분 문제의 최적해를 구한다.(상향식)

DP 적용 문제 : 피보나치 수열 pseudocode

fibo_dp(n) 
	f[0] <- 0
    f[1] <- 1
    for i in 2 -> n
    	f[i] <- f[i-1] + f[i-2]
    return f[n]