알고리즘

동적 계획법(Dynamic Programming, DP)이란?

2026.05.03

1. DP란 무엇인가?

동적 계획법(Dynamic Programming, DP) 은 하나의 큰 문제를 작은 하위 문제들로 나눈 뒤, 하위 문제의 값를 저장해 두고 재활용하여 전체 문제의 효율성을 극대화하는 기법이다.

핵심 컨셉: "이미 계산한 값은 메모리에 저장해 두고 다시 계산하지 않는다!"
시간 복잡도 혁신: 단순 재귀 호출 시 지수 시간 $O(2^N)$ 이 걸리는 문제를, 선형 시간 $O(N)$ 또는 다항 시간 내로 대폭 감축한다.

2. DP 사용 조건

모든 문제에 DP를 적용할 수 있는 것은 아니다.

아래 2가지 조건이 동시에 성립 할 때 DP 알고리즘을 적용할 수 있다.

① 최적 부분 구조

큰 문제의 최적해가 작은 하위 문제들의 최적해를 조합하여 형성되는 구조다.

예시: $N$ 번째 피보나치 수 $F(N)$ 을 구하려면, 하위 문제인 $F(N-1)$ 과 $F(N-2)$ 의 최적해를 구해 더하면 된다.

② 중복되는 부분 문제

동일한 작은 하위 문제가 반복해서 계속 등장하는 구조다.

위 다이어그램처럼 $F(5)$ 를 구할 때 $F(3)$ , $F(2)$ 등의 함수가 여러 트라이벌 가지에서 똑같이 재호출되는 현상을 말한다.

3. DP 구현 방식

DP를 코드 구현하는 방식은 크게 Top-Down(하향식) 과 Bottom-Up(상행식) 으로 나뉜다.

비교 항목	Top-Down (하향식)	Bottom-Up (상행식)
주요 기법	재귀(Recursion) + 메모이제이션(Memoization)	반복문(Loop) + 태뷸레이션(Tabulation)
방향	큰 문제 $\rightarrow$ 작은 문제로 분할	작은 문제부터 차례대로 $\rightarrow$ 큰 문제 완성
장점	점화식을 직관적으로 코드로 옮기기 쉬움	재귀 오버헤드 및 스택 오버플로우 위험 없음
단점	재귀 호출 깊이(Call Stack) 한계 가능성	초기 DP 테이블 정의 및 점화식 설계 필요

💻 구현 방식별 코드 비교 (피보나치 수열)

Top-Down 방식 (재귀 + 메모이제이션)

const memo = {};

function fiboTopDown(n) {
  if (n <= 1) return n;

  // 이미 계산한 적이 있다면 저장된 값을 즉시 반환 (기억하기)
  if (memo[n] !== undefined) return memo[n];

  // 계산 결과를 메모에 저장하며 반환
  memo[n] = fiboTopDown(n - 1) + fiboTopDown(n - 2);
  return memo[n];
}

Bottom-Up 방식 (반복문 + 태뷸레이션)

function fiboBottomUp(n) {
  if (n <= 1) return n;

  // DP 테이블 생성 및 초기값 설정
  const dp = new 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];
}

4. DP 동작 원리

DP가 수행되는 전체 메커니즘은 아래의 4단계 프로세스로 진행된다.

[1단계] 상태 정의 ➔ [2단계] 점화식 도출 ➔ [3단계] Base Case 설정 ➔ [4단계] 값 저장 및 재활용

1️⃣ Step 1: 상태 정의

dp 테이블/배열의 인덱스(i)가 나타낼 의미를 명확히 정의
예시: dp[i] = $i$번째 단계까지 도달했을 때 얻을 수 있는 최댓값

2️⃣ Step 2: 점화식 도출

큰 문제 dp[i]를 해결하기 위해 이전 하위 문제들(dp[i-1], dp[i-2] 등)과의 수학적 관계식을 세움
예시: $dp[i] = \max(dp[i-1], dp[i-2]) + cost[i]$

3️⃣ Step 3: Base Case 설정

더 이상 쪼개지지 않는 가장 작은 문제의 초기값을 명시적으로 할당
예시: dp[0] = 0, dp[1] = 1

4️⃣ Step 4: 값 저장 및 재활용

연산 과정에서 한 번 계산된 dp[i] 결과는 테이블에 저장
이후 동일한 계산 요청이 들어올 때 재연산 없이 즉시 반환하여 $O(1)$ 의 시간 복잡도를 보장한다.