동적 프로그래밍 — DP가 어려운 진짜 이유와 접근법

DP가 어려운 이유는 알고리즘 자체가 아니라, 문제를 보고 점화식을 떠올리는 과정 에 있습니다. 상태를 어떻게 정의하느냐에 따라 풀이가 완전히 달라지기 때문입니다.

정렬이나 탐색은 패턴이 명확합니다. 반면 DP는 문제마다 상태 정의가 달라지고 전이 방식도 제각각입니다. 하지만 핵심 원리를 제대로 잡고, 점화식을 세우는 사고 과정에 익숙해지면 풀 수 있는 범위가 넓어집니다.

개념 정의

동적 프로그래밍(DP) 은 큰 문제를 작은 하위 문제로 쪼개고, 그 결과를 저장해서 다시 계산하지 않는 기법입니다. 분할 정복과의 핵심 차이는 중복 부분 문제(Overlapping Subproblems) 의 유무입니다.

	분할 정복	DP
하위 문제 중복	없음	있음
하위 문제 결과 저장	안 함	함 (메모이제이션/테이블)
대표 예시	머지 소트, 퀵 소트	피보나치, 배낭 문제

머지 소트에서 [3, 1]과 [4, 2]를 각각 정렬할 때, 이 두 하위 문제는 서로 겹치지 않습니다. 반면 피보나치에서 fib(5)를 구하려면 fib(3)이 두 번 필요하고, fib(2)는 세 번 필요합니다. 이렇게 같은 하위 문제가 반복해서 등장하면 DP를 적용할 수 있습니다.

DP 적용의 두 가지 조건

1. 최적 부분 구조 (Optimal Substructure)

전체 문제의 최적해가 하위 문제의 최적해로부터 구성될 수 있어야 합니다.

예를 들어 서울에서 부산까지 최단 경로를 구할 때, 서울→대전 최단 경로와 대전→부산 최단 경로를 합치면 서울→부산 최단 경로가 됩니다. 이게 최적 부분 구조입니다.

2. 중복 부분 문제 (Overlapping Subproblems)

동일한 하위 문제가 여러 번 반복되어야 합니다.

이 두 조건이 동시에 만족되면 DP를 적용할 수 있고, 둘 중 하나라도 빠지면 다른 접근법을 써야 합니다. 최적 부분 구조만 있고 중복이 없으면 분할 정복, 중복은 있지만 최적 부분 구조가 아닌 경우는 단순 메모이제이션으로 풀 수 있습니다.

Top-Down vs Bottom-Up

DP를 구현하는 방식은 두 가지입니다.

Top-Down (메모이제이션)

재귀로 큰 문제부터 시작해서 아래로 내려가되, 이미 풀었던 하위 문제는 캐시에서 바로 꺼내 씁니다.

JAVA

int[] memo = new int[n + 1];
Arrays.fill(memo, -1);

int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

장점은 필요한 하위 문제만 계산한다는 것. 단점은 재귀 호출 스택이 깊어질 수 있다는 겁니다. Java 기본 스택 크기로는 대략 수천~만 단위 깊이에서 StackOverflowError가 터지니까, 입력 범위가 크면 Bottom-Up이 안전합니다.

Bottom-Up (타뷸레이션)

가장 작은 하위 문제부터 테이블을 채워 올라갑니다. 반복문 기반이라 스택 걱정이 없습니다.

JAVA

int fib(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

피보나치로 보는 최적화 단계

피보나치 수열을 통해 DP의 진화 과정을 단계별로 보겠습니다.

1단계: 순수 재귀 — O(2^n)

JAVA

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

fib(50)만 호출해도 연산량이 폭발합니다. 같은 값을 수없이 다시 계산하니까요.

2단계: 메모이제이션 — O(n)

JAVA

int[] memo = new int[n + 1];
Arrays.fill(memo, -1);

int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fib(n - 1) + fib(n - 2);
}

한번 계산한 값을 저장하니까 각 fib(i)는 최대 한 번만 계산됩니다. 시간복잡도가 O(2^n)에서 O(n)으로 뚝 떨어집니다.

3단계: 타뷸레이션 — O(n) 시간, O(n) 공간

JAVA

int fib(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

재귀 오버헤드를 완전히 제거한 버전입니다.

4단계: 공간 최적화 — O(n) 시간, O(1) 공간

JAVA

int fib(int n) {
    if (n <= 1) return n;
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

dp[i]를 계산할 때 필요한 건 직전 두 값뿐이니까, 배열 전체를 유지할 필요가 없습니다. 이 패턴은 DP 문제에서 정말 자주 쓰이는 최적화입니다.

점화식 세우는 사고 과정

DP에서 가장 어려운 부분이 이겁니다. 세 단계로 나눠서 생각하면 좀 수월해집니다.

1. 상태 정의

dp[i]가 무엇을 의미하는지 명확하게 정합니다.

예를 들어 계단 오르기 문제에서 dp[i]는 "i번째 계단에 도달하는 방법의 수"입니다. 이 정의가 흔들리면 전이 관계를 세울 수 없으니, 여기서 시간을 쓰는 게 맞습니다.

2. 전이 관계 (점화식)

dp[i]를 이전 상태들로 표현합니다.

한 번에 1칸 또는 2칸을 오를 수 있다면, i번째 계단에 도달하려면 i-1에서 1칸 오르거나 i-2에서 2칸 오르는 수밖에 없습니다.

PLAINTEXT

dp[i] = dp[i-1] + dp[i-2]

3. 기저 조건

재귀든 반복문이든 시작점이 필요합니다. dp[0] = 1 (바닥에 서 있는 경우), dp[1] = 1 (첫 번째 계단은 1가지).

이 세 단계가 DP 문제를 푸는 프레임워크입니다. 문제가 바뀌어도 이 흐름은 동일합니다.

대표 문제들

계단 오르기

위에서 다뤘으니 코드만 정리하겠습니다.

JAVA

int climbStairs(int n) {
    if (n <= 2) return n;
    int prev2 = 1, prev1 = 2;
    for (int i = 3; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

시간 O(n), 공간 O(1). 피보나치와 본질적으로 같은 문제입니다.

0/1 배낭 문제 (Knapsack)

무게 제한이 있는 배낭에 물건을 넣어 가치를 최대화하는 문제. 각 물건은 넣거나 안 넣거나 둘 중 하나입니다.

**상태 정의 **: dp[i][w] = 처음 i개 물건으로 무게 w까지 채울 때 최대 가치

** 점화식 **: i번째 물건을 넣을 수 있으면(무게가 w 이하면) 넣는 경우와 안 넣는 경우 중 큰 값을 취합니다.

JAVA

int knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[][] dp = new int[n + 1][capacity + 1];

    for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= capacity; w++) {
            dp[i][w] = dp[i - 1][w]; // i번째 물건 안 넣음
            if (weights[i - 1] <= w) {
                dp[i][w] = Math.max(dp[i][w],
                    dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            }
        }
    }
    return dp[n][capacity];
}

시간 O(n * W), 공간 O(n * W). 1차원 배열로 최적화하면 공간을 O(W)로 줄일 수 있습니다. 이때 주의할 점은 w를 역순으로 순회 해야 같은 물건을 두 번 쓰는 걸 방지한다는 겁니다.

JAVA

int knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[] dp = new int[capacity + 1];

    for (int i = 0; i < n; i++) {
        for (int w = capacity; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

LCS (Longest Common Subsequence)

두 문자열에서 순서를 유지하면서 공통으로 나타나는 가장 긴 부분 수열을 구합니다.

**상태 정의 **: dp[i][j] = 첫 번째 문자열의 앞 i글자와 두 번째 문자열의 앞 j글자에서의 LCS 길이

JAVA

int lcs(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[][] dp = new int[m + 1][n + 1];

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

시간 O(m * n), 공간 O(m * n). 문자가 같으면 대각선에서 +1, 다르면 위쪽이나 왼쪽 중 큰 값. 외우려 하지 말고 왜 그렇게 되는지 따져 보면 자연스럽습니다.

LIS (Longest Increasing Subsequence)

배열에서 순서를 유지하면서 증가하는 가장 긴 부분 수열입니다.

JAVA

// O(n²) DP 풀이
int lis(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);

    int maxLen = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxLen = Math.max(maxLen, dp[i]);
    }
    return maxLen;
}

dp[i]는 nums[i]로 끝나는 LIS 길이입니다. 이전 원소들을 하나씩 확인하면서, 현재보다 작은 원소의 LIS에 자기 자신을 이어붙일 수 있으면 갱신합니다.

이진 탐색을 활용하면 O(n log n)으로 개선 가능한데, O(n²) 풀이를 먼저 이해한 뒤 최적화 방향을 파악하는 게 좋습니다.

동전 교환 (Coin Change)

주어진 동전 종류로 목표 금액을 만들 때 필요한 최소 동전 수.

JAVA

int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1); // 불가능한 값으로 초기화
    dp[0] = 0;

    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

dp[i] = 금액 i를 만드는 데 필요한 최소 동전 수. 각 금액에 대해 모든 동전을 시도해 봅니다. dp[amount + 1]로 초기화하는 이유는 절대 나올 수 없는 값(어떤 금액이든 동전 1원짜리로만 만들어도 amount개를 넘지 않으니까)으로 불가능 상태를 표시하기 위해서입니다.

코딩 테스트에서 DP 문제 알아보는 법

DP 문제를 인식하는 게 반은 푼 겁니다. 아래 신호들을 기억해 두세요.

"최소", "최대", "경우의 수"를 구하라 — 최적화나 카운팅 문제는 DP일 가능성이 높습니다.
** 선택에 제약이 있다** — "연속으로 두 개를 선택할 수 없다", "무게 제한이 있다" 같은 조건이 붙으면 DP를 의심하세요.
** 그리디로 풀면 반례가 나온다** — 동전 교환에서 동전이 [1, 3, 4]이고 목표가 6일 때, 그리디는 4+1+1 = 3개를 내놓지만 최적은 3+3 = 2개입니다.
** 입력 크기가 애매하다** — n이 10^3~10^4 정도면 O(n²) DP, 10^5 정도면 O(n log n) 최적화가 필요한 DP일 수 있습니다.
** 부분 문제로 쪼갤 수 있다** — "i번째까지의 결과"를 정의할 수 있으면 DP 가능성이 높습니다.

주의할 점

Top-Down에서 StackOverflowError

Top-Down(메모이제이션)은 재귀 기반이기 때문에, 입력 범위가 10만 이상이면 Java 기본 스택 크기에서 StackOverflowError가 발생할 수 있습니다. 입력 범위가 클 때는 Bottom-Up을 선택하는 것이 안전합니다.

배낭 문제 공간 최적화 시 순회 방향 실수

1차원 DP 배열로 최적화할 때, w를 ** 순방향 **으로 순회하면 같은 물건을 중복 선택하는 버그가 생깁니다. 이미 갱신된 dp[w - weights[i]] 값을 참조하게 되기 때문입니다. 반드시 ** 역순 **으로 순회해야 이전 상태(i-1번째까지의 결과)를 참조합니다.

그리디로 풀 수 있는지 판단 실패

동전 교환에서 동전이 [1, 3, 4]이고 목표가 6일 때, 그리디는 4+1+1 = 3개를 내놓지만 최적은 3+3 = 2개입니다. 그리디가 먹히는 문제는 DP로도 풀 수 있지만, 그 반대는 성립하지 않습니다.

	그리디	DP
선택	현재 시점에서 최선	모든 경우를 고려
되돌림	없음	있음 (하위 문제 재활용)
정당성	탐욕 선택 속성 증명 필요	최적 부분 구조 확인
시간복잡도	보통 O(n log n) 이하	상태 수 × 전이 비용

DP 시간복잡도 분석

DP의 시간복잡도는 ** 상태 수 × 각 상태에서의 전이 비용 **으로 계산합니다.

문제	상태 수	전이 비용	시간복잡도
피보나치	n	O(1)	O(n)
0/1 배낭	n × W	O(1)	O(nW)
LCS	m × n	O(1)	O(mn)
LIS (기본)	n	O(n)	O(n²)

2D DP

상태가 두 개 이상의 변수에 의존할 때 사용합니다. 배낭 문제의 dp[i][w]가 전형적인 예시고, 격자(grid) 위에서 최소 비용 경로를 구하는 문제도 2D DP에 해당합니다.

JAVA

// 격자 최소 비용 경로
int minPathSum(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] dp = new int[m][n];
    dp[0][0] = grid[0][0];

    for (int i = 1; i < m; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];
    for (int j = 1; j < n; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];

    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
        }
    }
    return dp[m - 1][n - 1];
}

비트마스크 DP

상태를 비트마스크로 표현하는 기법입니다. 원소가 n개일 때 "어떤 원소들을 선택했는가"를 2^n 가지 비트마스크로 나타냅니다.

대표 문제가 ** 외판원 문제(TSP)**인데, n개의 도시를 모두 방문하고 돌아오는 최소 비용을 구할 때 사용합니다. 상태 정의는 dp[visited][current] = 방문 상태가 visited이고 현재 current에 있을 때 최소 비용입니다.

먼저 초기화와 DP 테이블 채우기를 보겠습니다.

JAVA

int INF = Integer.MAX_VALUE / 2;
int[][] dp = new int[1 << n][n];
for (int[] row : dp) Arrays.fill(row, INF);
dp[1][0] = 0; // 0번 도시에서 출발

각 방문 상태(mask)에서, 현재 위치(u)에서 아직 방문하지 않은 도시(v)로 이동하며 최솟값을 갱신합니다.

JAVA

for (int mask = 1; mask < (1 << n); mask++) {
    for (int u = 0; u < n; u++) {
        if (dp[mask][u] == INF || (mask & (1 << u)) == 0) continue;
        for (int v = 0; v < n; v++) {
            if ((mask & (1 << v)) != 0) continue; // 이미 방문
            int nextMask = mask | (1 << v);
            dp[nextMask][v] = Math.min(dp[nextMask][v],
                dp[mask][u] + dist[u][v]);
        }
    }
}

모든 도시를 방문한 후 출발점으로 돌아오는 최소 비용을 구합니다.

JAVA

int allVisited = (1 << n) - 1;
int ans = INF;
for (int u = 1; u < n; u++) {
    ans = Math.min(ans, dp[allVisited][u] + dist[u][0]);
}

시간 O(2^n * n²), 공간 O(2^n * n). n이 20 정도까지만 현실적으로 풀 수 있습니다.

파생 개념

DP를 공부하다 보면 자연스럽게 만나게 되는 주제들입니다.

그리디 알고리즘

그리디는 매 단계에서 지역적으로 최적인 선택을 하고 되돌아보지 않습니다. 활동 선택 문제, 허프만 코딩, 크루스칼 알고리즘 같은 곳에서 쓰이는데, 핵심은 탐욕 선택 속성(Greedy Choice Property) 을 만족하는지 증명할 수 있어야 한다는 것입니다.

DP가 모든 경우를 탐색한 후 최적을 고르는 거라면, 그리디는 탐색 없이 바로 선택합니다. 그래서 시간복잡도가 대체로 낮지만, 적용 범위도 좁습니다.

분할 정복

DP와 뿌리가 같습니다. 둘 다 문제를 쪼개서 풀죠. 차이점은 앞에서 말한 대로 하위 문제가 겹치냐 안 겹치냐. 머지 소트, 퀵 소트, 이진 탐색이 분할 정복의 대표입니다. 하위 문제가 독립적이라 메모이제이션이 필요 없습니다.

그래프 최단 경로 — 다익스트라

다익스트라 알고리즘은 DP의 원리를 그래프에 적용한 것으로 볼 수 있습니다. 출발점에서 각 노드까지의 최단 거리를 갱신해 나가는 과정 자체가 "이전에 계산한 최적값을 활용해서 다음 값을 구한다"는 DP의 사고방식이거든요.

다만 다익스트라는 그리디 성격도 가지고 있습니다. 매 단계에서 아직 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택하니까요. 그래서 음수 가중치가 있으면 쓸 수 없고, 그때는 벨만-포드(DP 기반)를 사용합니다.

정리

항목	핵심
DP 적용 조건	최적 부분 구조 + 중복 부분 문제
Top-Down	재귀 + 메모이제이션, 필요한 것만 계산, 스택 위험
Bottom-Up	반복문 + 테이블, 스택 안전, 모든 상태 계산
점화식 세우기	상태 정의 → 전이 관계 → 기저 조건
공간 최적화	직전 상태만 필요하면 배열 대신 변수 2~3개로 가능
시간복잡도	상태 수 × 전이 비용
DP 인식 신호	"최소/최대/경우의 수", 선택 제약, 그리디 반례

점화식이 바로 안 떠오르면, n=1, n=2, n=3일 때 결과를 직접 손으로 써보세요. 작은 예시에서 규칙이 보이는 경우가 많습니다.