DP 사고법: 상태, 전이, 초기값 설계

DP는 점화식 암기보다 상태 정의가 우선입니다. 상태가 틀리면 전이와 초기값도 함께 틀려서 코드 전체가 흔들립니다. 그래서 코드를 쓰기 전에 dp[...] 의미를 문장으로 우선 고정해야 합니다.

공식을 외워 대입하면 조건이 조금만 바뀌어도 막히기 쉽습니다. 여기서는 상태-전이-초기값을 설계하는 절차를 반복해 익히는 데 집중합니다. 새 DP 문제를 만나도 같은 순서로 구조를 세우는 것을 목표로 합니다.

DP 상태-전이-초기값 설계 청사진

핵심 개념 청사진

DP는 점화식을 쓰기 전에 상태 의미를 고정하면 절반은 끝납니다. 코드를 시작하기 전에 dp[...]가 무엇을 뜻하는지 한 문장으로 우선 적어 보세요.

상태(state)는 부분문제 정답을 저장하는 칸의 의미입니다. 정확히는 재사용 가능한 부분해를 인덱스로 식별한 변수 집합이며, 이 정의가 흔들리면 전이도 함께 흔들립니다. dp[i]를 "0..i 구간에서 가능한 최대 합"으로 정하면 이후 계산 방향이 명확해집니다.

전이(transition)는 이미 계산된 작은 상태를 이용해 현재 상태 값을 만드는 규칙입니다. 상태 그래프에서 선행 상태의 결과를 결합해 현재 최적값을 만드는 점화식이라고 보면 됩니다. 인접 금지 최대 합은 dp[i]=max(dp[i-1], nums[i]+dp[i-2])처럼 선택/미선택 두 경우를 비교해 전이합니다.

초기값(base case)은 점화식을 시작할 기준 상태입니다. 공집합, 첫 원소, 최소 인덱스 같은 경계 입력의 정답을 명시해 전이식이 안정적으로 동작하게 만듭니다. 공집합 합을 0으로 두고 첫 상태를 0 또는 nums[0]으로 두는 선택은 상태 정의에 맞춰 결정해야 합니다.

상태 설계가 실무에서 중요한 이유

DP 실패의 핵심 원인은 수학이 아니라 의미 불일치입니다. 예를 들어 dp[i]를 i번째를 반드시 선택으로 잡았는지, i번째까지 고려했을 때 최적으로 잡았는지에 따라 같은 코드라도 완전히 다른 결과가 나옵니다.

초기값 또한 상태 정의에 종속됩니다. 상태가 모호하면 0, -INF, INF 중 무엇을 넣어야 할지 결정할 수 없습니다.

상태 전이 오답 재현으로 검증하기

오답 -> 디버깅 -> 교정 -> 검증 순서를 먼저 고정하고 예제를 따라가면 경계 버그를 빠르게 줄일 수 있습니다.

1차원 DP 상태 정의를 작은 배열로 따라가 봅니다.

문제: 인접한 원소를 동시에 고를 수 없을 때 최대 합
입력: [2, 7, 9, 3, 1]

dp[i]를 0..i 구간에서 얻을 수 있는 최대 합으로 정의합니다.
전이는 take = nums[i] + dp[i-2], skip = dp[i-1]로 나눕니다.
각 단계에서 max(take, skip)를 기록하면 최종 답은 dp[n-1]입니다.
상태 의미가 흔들리면 초기값과 전이식이 함께 깨집니다.

1차원 상태 설계 적용 관점

문제를 읽을 때 아래 신호가 보이면 DP를 우선 검토합니다.

부분문제 정답을 재사용할 수 있다.
같은 계산이 반복된다.
선택 결과가 이전 상태에만 의존한다.
탐욕 적용 관점을 증명하기 어렵다.

반대로 상태 차원이 과도하게 커지면 DP 대신 그리디, 이분 탐색, 그래프 탐색을 우선 비교해야 합니다.

DP 기초: 인접 금지 최대 합(1차원 DP)

문제 의도: 상태/전이/초기값을 명확히 정의해 1차원 DP 설계를 연습합니다.
입력 예시: arr=[2,7,9,3,1]
출력 예시: 12

main.cpp

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int maxNonAdjacentSum(const vector<int>& nums) {
    if (nums.empty()) return 0;
    vector<int> dp(nums.size(), 0);
    dp[0] = nums[0];
    for (int i = 1; i < (int)nums.size(); ++i) {
        int take = nums[i] + (i >= 2 ? dp[i - 2] : 0);
        int skip = dp[i - 1];
        dp[i] = max(take, skip);
    }
    return dp.back();
}

int main() {
    vector<int> arr = {2, 7, 9, 3, 1};
    cout << maxNonAdjacentSum(arr) << "\n";
    return 0;
}

Main.java

public class Main {
    static int maxNonAdjacentSum(int[] nums) {
        if (nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int take = nums[i] + (i >= 2 ? dp[i - 2] : 0);
            int skip = dp[i - 1];
            dp[i] = Math.max(take, skip);
        }
        return dp[nums.length - 1];
    }

    public static void main(String[] args) {
        int[] arr = {2, 7, 9, 3, 1};
        System.out.println(maxNonAdjacentSum(arr));
    }
}

main.py

def max_non_adjacent_sum(nums):
    if not nums:
        return 0

    # dp[i]: 0..i 구간에서 인접하지 않게 고를 때 최대 합
    dp = [0] * len(nums)
    dp[0] = nums[0]

    for i in range(1, len(nums)):
        take = nums[i] + (dp[i - 2] if i >= 2 else 0)
        skip = dp[i - 1]
        dp[i] = max(take, skip)

    return dp[-1]

arr = [2, 7, 9, 3, 1]
print(max_non_adjacent_sum(arr))
# 출력: 12

main.rs

fn max_non_adjacent_sum(nums: &[i32]) -> i32 {
    if nums.is_empty() {
        return 0;
    }
    let mut dp = vec![0; nums.len()];
    dp[0] = nums[0];
    for i in 1..nums.len() {
        let take = nums[i] + if i >= 2 { dp[i - 2] } else { 0 };
        let skip = dp[i - 1];
        dp[i] = take.max(skip);
    }
    dp[nums.len() - 1]
}

fn main() {
    let arr = [2, 7, 9, 3, 1];
    println!("{}", max_non_adjacent_sum(&arr));
}

채택/비채택 상태 전개 상태 정의 조건 체크

상태를 i번째까지 고려한 최댓값으로 정의했기 때문에 전이는 선택/비선택 두 가지로 깔끔하게 분해됩니다. 이 문제에서 초기값 dp[0] = nums[0]은 상태 의미와 일치합니다.

평균 시간복잡도: O(N)
최악 시간복잡도: O(N)
공간복잡도: O(N)

DP 기초: 동전 교환 최소 개수

문제 의도: 불가능 상태(INF) 처리와 최소 전이 패턴을 확인합니다.
입력 예시: amount=11, coins=[1,2,5]
출력 예시: 3

main.cpp

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int minCoins(int amount, const vector<int>& coins) {
    const int INF = 1e9;
    vector<int> dp(amount + 1, INF);
    dp[0] = 0;
    for (int x = 1; x <= amount; ++x) {
        for (int c : coins) {
            if (x >= c && dp[x - c] != INF) {
                dp[x] = min(dp[x], dp[x - c] + 1);
            }
        }
    }
    return dp[amount] == INF ? -1 : dp[amount];
}

int main() {
    cout << minCoins(11, {1, 2, 5}) << "\n";
    return 0;
}

Main.java

import java.util.Arrays;

public class Main {
    static int minCoins(int amount, int[] coins) {
        int INF = 1_000_000_000;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, INF);
        dp[0] = 0;
        for (int x = 1; x <= amount; x++) {
            for (int c : coins) {
                if (x >= c && dp[x - c] != INF) {
                    dp[x] = Math.min(dp[x], dp[x - c] + 1);
                }
            }
        }
        return dp[amount] == INF ? -1 : dp[amount];
    }

    public static void main(String[] args) {
        System.out.println(minCoins(11, new int[]{1, 2, 5}));
    }
}

main.py

def min_coins(amount, coins):
    INF = 10**9
    # dp[x]: 금액 x를 만드는 최소 동전 개수
    dp = [INF] * (amount + 1)
    dp[0] = 0

    for x in range(1, amount + 1):
        for c in coins:
            if x >= c and dp[x - c] != INF:
                dp[x] = min(dp[x], dp[x - c] + 1)

    return -1 if dp[amount] == INF else dp[amount]

print(min_coins(11, [1, 2, 5]))
# 출력: 3

main.rs

fn min_coins(amount: usize, coins: &[usize]) -> i32 {
    let inf = 1_000_000_000_i32;
    let mut dp = vec![inf; amount + 1];
    dp[0] = 0;
    for x in 1..=amount {
        for &c in coins {
            if x >= c && dp[x - c] != inf {
                dp[x] = dp[x].min(dp[x - c] + 1);
            }
        }
    }
    if dp[amount] == inf { -1 } else { dp[amount] }
}

fn main() {
    println!("{}", min_coins(11, &[1, 2, 5]));
}

최소 개수 전이 체크

이 문제의 중요한 기준은 불가능 상태를 INF로 명확히 분리하는 것입니다. 초기값 dp[0] = 0이 없으면 모든 상태가 전파되지 못합니다. 전이 순서를 바꿔도 가능하지만, 현재 구현은 금액 기준 순회로 의미를 읽기 쉽게 유지합니다.

평균 시간복잡도: O(Amount * K)
최악 시간복잡도: O(Amount * K)
공간복잡도: O(Amount)

DP 기초: 메모이제이션 vs 테이블

문제 의도: 탑다운/바텀업 구현 차이와 적용 관점을 비교합니다.
입력 예시: n=10 (피보나치)
출력 예시: 두 방식 모두 55

main.cpp

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

long long fibSolve(int x, unordered_map<int, long long>& memo) {
    auto it = memo.find(x);
    if (it != memo.end()) {
        return it->second;
    }
    long long value = fibSolve(x - 1, memo) + fibSolve(x - 2, memo);
    memo[x] = value;
    return value;
}

long long fibTopDown(int n) {
    unordered_map<int, long long> memo{{0, 0}, {1, 1}};
    return fibSolve(n, memo);
}

long long fibBottomUp(int n) {
    if (n <= 1) return n;
    vector<long long> dp(n + 1, 0);
    dp[1] = 1;
    for (int i = 2; i <= n; ++i) dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

int main() {
    cout << fibTopDown(10) << " " << fibBottomUp(10) << "\n";
    return 0;
}

Main.java

import java.util.HashMap;
import java.util.Map;

public class Main {
    static long fibTopDown(int n) {
        Map<Integer, Long> memo = new HashMap<>();
        memo.put(0, 0L);
        memo.put(1, 1L);
        return solve(n, memo);
    }

    static long solve(int x, Map<Integer, Long> memo) {
        if (memo.containsKey(x)) return memo.get(x);
        long value = solve(x - 1, memo) + solve(x - 2, memo);
        memo.put(x, value);
        return value;
    }

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

    public static void main(String[] args) {
        System.out.println(fibTopDown(10) + " " + fibBottomUp(10));
    }
}

main.py

def fib_top_down(n):
    memo = {0: 0, 1: 1}

    def solve(x):
        if x in memo:
            return memo[x]
        memo[x] = solve(x - 1) + solve(x - 2)
        return memo[x]

    return solve(n)

def fib_bottom_up(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

print(fib_top_down(10), fib_bottom_up(10))
# 출력: 55 55

main.rs

use std::collections::HashMap;

fn fib_top_down(n: i32) -> i64 {
    fn solve(x: i32, memo: &mut HashMap<i32, i64>) -> i64 {
        if let Some(v) = memo.get(&x) {
            return *v;
        }
        let v = solve(x - 1, memo) + solve(x - 2, memo);
        memo.insert(x, v);
        v
    }

    let mut memo = HashMap::new();
    memo.insert(0, 0_i64);
    memo.insert(1, 1_i64);
    solve(n, &mut memo)
}

fn fib_bottom_up(n: usize) -> i64 {
    if n <= 1 {
        return n as i64;
    }
    let mut dp = vec![0_i64; n + 1];
    dp[1] = 1;
    for i in 2..=n {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    dp[n]
}

fn main() {
    println!("{} {}", fib_top_down(10), fib_bottom_up(10));
}