동적 계획법(DP)을 적용할 수 있는 문제의 특징은 무엇인가요?

동적 계획법(DP)은 큰 문제를 작은 부분 문제로 나누고, 이미 계산한 결과를 저장해 중복 계산을 피하는 기법입니다. 적용 가능한 핵심 특징은 최적 부분 구조와 중복 부분 문제입니다.

핵심 개념

• 최적 부분 구조는 전체 문제의 최적해가 부분 문제의 최적해로 구성될 수 있다는 뜻입니다.
• 중복 부분 문제는 같은 상태가 여러 경로에서 반복해서 등장한다는 뜻입니다.
• 상태 정의, 점화식, 초기값, 계산 순서가 DP 설계의 핵심입니다.

동작 방식 또는 판단 기준

이 주제를 이해할 때는 다음 순서로 보면 실무 적용이 쉬워집니다.

1. 무엇을 해결하려는가: 성능, 표현력, 안정성, 접근성 중 어떤 문제를 줄이려는지 확인합니다.
2. 전제 조건은 무엇인가: 정렬 여부, 브라우저 지원, 네트워크 특성, 동시성 조건처럼 성립해야 하는 조건을 점검합니다.
3. 비용은 어디서 발생하는가: 시간 복잡도, 메모리, 캐시, 재시도, 렌더링 비용처럼 병목 지점을 나눠 봅니다.
4. 실패 시 어떤 문제가 생기는가: 잘못 적용했을 때의 버그나 운영 리스크를 함께 고려합니다.

실제 예시

// 피보나치: 중복 부분 문제의 가장 단순한 예
function fib(n) {
  const dp = Array(n + 1).fill(0);
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

배낭 문제 상태 예:
dp[i][w] = i번째 물건까지 고려했고, 용량이 w일 때 얻을 수 있는 최대 가치

실무에서 주의할 점

• 상태를 너무 크게 잡으면 메모리와 시간이 폭발합니다.
• 점화식은 맞아도 계산 순서가 잘못되면 아직 계산되지 않은 값을 참조할 수 있습니다.
• 그리디로 풀 수 있는 문제에 DP를 쓰면 불필요하게 복잡해질 수 있습니다.

실무 적용 가이드

• 완전 탐색에서 같은 하위 문제가 반복되는지 먼저 봅니다.
• 재귀 + memoization으로 시작한 뒤 필요하면 bottom-up으로 바꿉니다.
• 상태 수 × 전이 비용으로 전체 복잡도를 계산합니다.

함께 연결해서 보면 좋은 키워드

Dynamic Programming, DP, Memoization, Optimal Substructure

정리

동적 계획법(DP)은 큰 문제를 작은 부분 문제로 나누고, 이미 계산한 결과를 저장해 중복 계산을 피하는 기법입니다. 다만 개념 자체보다 중요한 것은 적용 조건과 한계를 함께 이해하는 것입니다. 작은 예제에서는 단순해 보여도 실제 서비스에서는 성능, 보안, 유지보수성, 접근성 요구사항이 함께 얽히므로, 문제의 성격을 먼저 파악한 뒤 적절한 도구로 선택하는 것이 좋습니다.