[알고리즘] DP - Dynamic Programming(다이나믹 프로그래밍)

알고리즘을 공부하다 보면 DP라는 말을 간혹 접하게 되는 경우가 있다. 이 DP는 Dynamic Programming(다이나믹 프로그래밍)의 줄임말이다. 다이나믹 프로그래밍, 혹은 동적 프로그래밍이라 불리는 이것은 무엇일까?

 

1. 다이나믹 프로그래밍이란?

동적 계획법이라고도 불리는 다이나믹 프로그래밍은 큰 문제를 작은 문제로 나누어 푸는 알고리즘을 뜻한다. 동적으로 작동하는 프로그래밍이라는 직관적인 의미를 가지고 있지는 않다. Dynamic Programming이라고 이름을 붙인 사람도 이 말이 멋있게 느껴져 이 이름을 붙였다고 말한 바 있다.

 

2. 다이나믹 프로그래밍의 성립 조건

모든 문제를 다이나믹 프로그래밍으로 해결할 수 있는 것은 아니다. 이 알고리즘으로 문제를 해결하기 위해서는 두 가지 조건을 만족해야만 한다. 두 가지 조건은 다음과 같다.

1. 작은 문제가 반복적으로 일어난다.
2. 같은 문제는 구할 때마다 정답이 같다.

큰 문제와 작은 문제를 같은 방법으로 풀이하는 것이 가능하다. 작은 문제의 결과값이 항상 같다는 점을 이용하여 큰 문제를 해결하는 방식을 이용하기 때문이다. 또한 문제의 정답을 작은 문제의 정답에서 구할 수 있어야 한다. 따라서 정답을 구한 문제를 어딘가에 메모해 두고, 그보다 큰 문제를 풀게 되었을 경우 이전에 풀이했던 작은 문제의 결과값을 이용한다.

 

3. Memorization

앞에서 말했듯, 다이나믹 프로그래밍에서는 작은 문제들이 반복되며 이 작은 문제들의 결과값은 항상 같다. 이 특징을 이용하여 한 번 계산한 작은 문제를 저장해 놓고 다시 사용하게 되는데, 이것을 Memorization이라고 한다.

대표적인 예시는 바로 피보나치 수열이다. 피보나치 수열은 1, 1, 2, 3, 5, 8, 13...의 형태로 증가하게 된다. a, b, (a+b), b+(a+b)의 순으로 수가 증가하게 되는 것인데, 수가 커지게 되면 함수의 값도 기하급수적으로 증가하기 때문에 일정 수 이상의 수열을 구하기가 쉽지 않다. 그렇지만 위에서 말한 다이나믹 프로그래밍의 성립 조건 두 가지를 떠올려 보면, 그것을 이용하여 피보나치 수열을 풀 수 있다는 사실을 알 수 있다.

 

4. 다이나믹 프로그래밍의 구현 방법

• Botton-up
  
  문제를 해결할 때 처음부터 작은 문제로 시작하여 차근차근 해결하는 방향으로 나아가는 방법.
• Top-down
  
  큰 문제를 풀 때 작은 문제가 아직 해결되지 않았다면 그때 필요한 작은 문제를 해결한 후 다시 큰 문제를 해결하는 방법. 재귀 함수로 구현하는 경우 대부분 Top-down이다.

 

*코드 예시는 추후 추가하겠습니다.