[알고리즘] 동적 계획법 - Dynamic Programming

동적 계획법이란?

어떤 문제를 풀기 위해 그 문제를 더 작은 문제들로 나누고, 작은 문제들에서 구한 해를 어딘가에 저장한 다음 활용해 문제를 해결하는 알고리즘 설계 기법이다. DP는 이름처럼 다이내믹한 프로그래밍이라는 거리가 멀다. 단순히 붙여진 이름일 뿐이라고 한다.

 

 

 

분할 정복 방식과 차이점

DP의 문제 접근 방식은 기본적으로 '분할 정복 알고리즘(Divide and Conquer)'과 비슷하다. 두 경우 모두 문제를 부분으로 나누어 각 부분 문제의 답을 계산하고, 이 값을 이용해 원래 문제를 해결하는 과정이다. DP와 분할 정복의 차이는 부분 문제로 나누는 방식에 차이가 있다. DP는 작은 문제들이 반복적으로 사용되며 (즉, 답이 바뀌지 않음) 반대로 동적 계획법은 작은 문제가 중복이 발생하지 않고 단순히 나누어 푸는 방법이다.

 

 

DP 문제의 해결 순서

1. 큰 문제를 작은 문제로 나눈다.

2. 재귀적인 구조를 활용할 수 있는 점화식을 만든다.

3. 작은 문제의 도출 값을 메모하고, 큰 문제를 풀어나갈 때 작은 문제가 반복되면 메모한 값을 이용한다. (Memoization방식)

 

 

DP의 조건

1. 작은 문제가 반복, 중복이 일어나는 경우

2. 같은 문제의 값은 매번 같다.

 

여기서 반복적으로 중복이 일어난 부분이 있다. 원으로 표시한 부분만 아니라 F(4)와 F(3)을 구하기 위해 모두 F(2)를 계산해야한다. 이런 식으로 매번 다 계산을 하면 시간적으로 비효율적이다. 그래서 DP방식을 이용해 메모이제이션을 통해 값을 활용해서 문제를 해결하면 훨씬 빠른 계산이 가능해진다.