Dynamic Programming

DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다.

Richard Bellman이 1950년대에 사용한 단어로 이름은 그냥 멋있어 보여서 그렇게 지어졌으니 신경 쓰지 않아도 된다.
큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용한다. 그래서 혹자는 DP가 아닌 '기억하며 풀기'라고 부르기도 한다.

2. DP를 쓰는 이유

왜 DP를 사용할까? 사실 일반적인 재귀(Naive Recursion) 방식 또한 DP와 매우 유사하다. 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산될 수 있다는 것이다.

예를 들어 피보나치 수열을 살펴보자. 피보나치 수열은 아래와 같다.
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ...

피보나치 수를 구하고 싶을 때 재귀로 함수를 구성하면 어떻게 될까? 단순하다. return f(n) = f(n-1) + f(n-2)

그런데 f(n-1), f(n-2)에서 각 함수를 1번씩 호출하면 동일한 값을 2번씩 구하게 되고 이로 인해 100번째 피보나치 수를 구하기 위해 호출되는 함수의 횟수는 기하급수 적으로 증가한다.(약 7해, #,###경 #,###조 ... 번 이상 함수 호출, 컴퓨터도 죽는다.)

왜냐하면, f(n-1)에서 한 번 구한 값을 f(n-2)에서 또 다시 같은 값을 구하는 과정을 반복하게 되기 때문이다. 아래의 그림처럼 반복되는 계산을 또 하게 된다.