동적 계획법(Dynamic Programming)

동적 계획법(Dynamic Programming, DP)은 큰 문제를 작은 문제로 나누어 해결하고, 그 결과를 저장해두었다가 재사용하는 방식이다. 핵심 아이디어는 단순하다. 이미 한 번 계산한 값을 다시 계산하지 말자는 것이다. 계산 결과를 어딘가에 저장해두고, 같은 문제가 다시 등장하면 바로 꺼내서 사용하는 방식이다.

DP가 필요한 이유는 보통 같은 계산이 반복적으로 발생할 때다. 단순한 반복문이나 재귀로 문제를 풀면, 눈에 보이지 않게 같은 계산을 여러 번 수행하는 경우가 많다. 이때 DP를 사용하면 불필요한 반복을 제거할 수 있고, 시간 복잡도를 크게 줄일 수 있다.

하지만 모든 문제에 DP를 적용할 수 있는 것은 아니다. DP가 의미를 가지려면 반드시 두 가지 조건이 만족되어야 한다.

첫 번째 조건은 부분 문제의 중복이다. 문제를 작은 단위로 나눴을 때, 동일한 하위 문제가 여러 번 등장해야 한다. 예를 들어 어떤 값을 구하기 위해 이전 값들을 참고해야 하는 상황에서, 같은 값이 계속 필요해진다면 이 조건을 만족한다. 만약 모든 하위 문제가 매번 새롭고 한 번만 사용된다면, 저장해두는 것 자체가 의미가 없다.

두 번째 조건은 최적 부분 구조다. 이는 큰 문제의 정답이, 그보다 작은 문제들의 정답을 조합해서 만들어질 수 있다는 뜻이다. 즉, 전체 문제의 최적해를 구하는 과정에서 중간 단계의 선택 역시 항상 최적이어야 한다. 작은 문제에서 이미 최적이 아닌 선택을 해버리면, 나중에 아무리 잘 조합해도 전체 최적해를 만들 수 없다. 이런 구조가 있어야 DP가 성립한다.

이 두 조건을 동시에 만족하는 대표적인 예가 피보나치 수열이다. 피보나치 수는 F(n) = F(n-1) + F(n-2) 형태로 정의된다. 여기서 F(n-1)과 F(n-2)는 여러 곳에서 반복해서 사용된다. 또한 F(n)의 값은 바로 이전 두 값의 합으로 결정되므로, 작은 문제의 결과가 큰 문제의 결과를 직접 구성한다. 그래서 DP가 잘 맞는다.

DP를 구현하는 방식은 크게 두 가지가 있다. 탑다운 방식과 바텀업 방식이다. 탑다운은 재귀를 사용해 큰 문제부터 풀어 내려가면서, 이미 계산한 값은 메모해두고 다시 계산하지 않는 방식이다. 흔히 메모이제이션이라고 부른다. 반면 바텀업은 가장 작은 문제부터 차례대로 값을 채워 나가면서, 최종적으로 원하는 답을 구하는 방식이다. 반복문을 사용하는 경우가 많다.

중요한 점은, DP를 쓴다는 것은 단순히 “배열 하나 더 쓰는 것”이 아니라는 것이다. 문제를 어떻게 쪼갤지, 어떤 값을 저장할지, 그 값이 다음 계산에 어떻게 사용되는지를 먼저 명확히 정의해야 한다. 이 설계가 제대로 되지 않으면 DP는 오히려 코드를 복잡하게 만들 뿐이다.

DP는 문제를 작은 문제로 나눌 수 있고, 그 작은 문제들이 반복해서 등장하며, 작은 문제의 정답이 모여 큰 문제의 정답을 만드는 구조일 때 DP를 사용하면 된다.