동적 프로그래밍(Dynamic Programming)이란?
동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 더 작고 단순한 하위 문제(sub-problem)로 분할하여 해결하는 알고리즘 설계 기법입니다. 중요한 점은 각 하위 문제를 독립적으로 처리하는 것이 아니라는 것입니다. 한 번 계산된 하위 문제의 결과는 메모리에 저장되며, 이후 유사하거나 중복되는 하위 문제를 만났을 때 다시 계산하지 않고 저장된 결과를 그대로 재활용합니다.
이러한 특성 덕분에 동적 프로그래밍은 불필요한 중복 연산을 제거하여 실행 속도를 크게 향상시킬 수 있습니다. 대표적인 예로 피보나치 수열 계산이 있는데, 단순 재귀로 구현하면 지수 시간이 걸리지만 동적 프로그래밍을 적용하면 선형 시간으로 최적화할 수 있습니다.
동적 프로그래밍의 적용 조건
동적 프로그래밍은 문제를 유사한 하위 문제들로 나눌 수 있고, 그 결과를 반복해서 재사용할 수 있을 때 효과적으로 활용됩니다. 주로 최적화(Optimization) 문제에 사용되며, 알고리즘은 현재 하위 문제를 풀기 전에 먼저 이전에 해결한 하위 문제들의 결과를 살펴본 뒤, 이를 조합하여 전체 문제의 최적해를 도출합니다.
특정 문제에 동적 프로그래밍을 적용하기 위해서는 다음 세 가지 조건이 충족되어야 합니다.
- 중복되는 하위 문제(Overlapping Sub-problems): 문제를 더 작은 하위 문제로 나눌 수 있어야 하며, 나눠진 하위 문제들이 서로 겹쳐서 반복적으로 등장해야 합니다.
- 최적 부분 구조(Optimal Substructure): 작은 하위 문제들의 최적해를 결합하여 전체 문제의 최적해를 구할 수 있어야 합니다.
- 메모이제이션(Memoization): 한 번 계산한 하위 문제의 결과를 저장하고 재사용하는 기법이 활용됩니다.
동적 프로그래밍의 두 가지 접근 방식
동적 프로그래밍 문제는 크게 두 가지 방식으로 해결할 수 있습니다.
1. 상향식(Bottom-Up) 접근
상향식 접근에서는 먼저 문제를 분석하여 하위 문제들이 어떤 순서로 해결되어야 하는지 파악합니다. 가장 단순하고 자명한(trivial) 하위 문제부터 시작하여 점차 확장해 나가면서 최종적으로 주어진 원래 문제의 답을 도출합니다. 일반적으로 반복문(loop)을 사용해 구현하며, '타뷸레이션(Tabulation)'이라고도 불립니다.
// 피보나치 수열 - 상향식(Bottom-Up) 예시
function fibonacci(n) {
const dp = [0, 1];
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2]; // 이전 결과를 저장하고 재활용
}
return dp[n];
}2. 하향식(Top-Down) 접근
하향식 접근은 주어진 문제 자체부터 시작하여 이를 더 작은 하위 문제로 분해하면서 해결해 나갑니다. 재귀 호출을 기반으로 구현되며, 특정 하위 문제가 이미 해결된 적이 있다면 저장해 둔 결과를 즉시 반환하여 불필요한 재계산을 피합니다. 이 방식은 흔히 '메모이제이션(Memoization)'이라고 불립니다.
// 피보나치 수열 - 하향식(Top-Down) 예시
const memo = {};
function fibonacci(n) {
if (n <= 1) return n;
if (memo[n]) return memo[n]; // 이미 계산한 결과라면 즉시 반환
memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
return memo[n];
}마무리
동적 프로그래밍은 중복 연산을 줄여 성능을 극대화하는 강력한 기법입니다. 문제가 중복되는 하위 문제와 최적 부분 구조를 가지고 있다면, 상향식 또는 하향식 접근을 통해 효율적인 해결책을 설계할 수 있습니다. 자바스크립트에서도 배열이나 객체를 활용해 손쉽게 메모이제이션을 구현할 수 있으므로, 코딩 테스트나 실무 알고리즘 문제 해결에 꼭 익혀두면 큰 도움이 됩니다.