동적 프로그래밍 (DP) — 1차원

관련 문제

문제	난이도	핵심
피보나치 수	Lv.2	DP 기초
계단 오르기	Lv.2	조건부 점화식
N으로 표현	Lv.3	1차원 DP 응용

---

1. 개념

DP(Dynamic Programming)는 큰 문제를 작은 문제로 나누고, 작은 문제의 결과를 저장해서 재사용하는 방식이다.

핵심은 두 가지다.

• 중복 부분 문제 — 같은 계산이 반복된다
• 최적 부분 구조 — 작은 문제의 최적해가 큰 문제의 최적해를 만든다

피보나치를 재귀로 풀면?

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2) ← 중복
│   │   └── fib(1)
│   └── fib(2) ← 중복
└── fib(3) ← 중복

같은 계산을 계속 반복한다. DP는 이걸 한 번만 계산하고 저장해서 꺼내 쓴다.

---

2. 동작 과정

피보나치 — fib(5) 계산

i	점화식	dp[i]
0	초기값	0
1	초기값	1
2	dp[0] + dp[1]	1
3	dp[1] + dp[2]	2
4	dp[2] + dp[3]	3
5	dp[3] + dp[4]	5

앞에서부터 채워나가기 때문에 각 값은 딱 한 번만 계산된다.

---

3. 구현 방식 2가지

Top-Down (메모이제이션)

재귀로 내려가면서 결과를 저장한다.

int[] memo = new int[100];

int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];  // 이미 계산했으면 바로 반환
    return memo[n] = fib(n - 1) + fib(n - 2);
}

Bottom-Up (타뷸레이션)

작은 문제부터 순서대로 채워나간다. 코테에서는 이 방식을 더 많이 쓴다.

int fib(int 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. 핵심 포인트 2가지

점화식을 먼저 세워라

코드보다 점화식이 먼저다. dp[i]가 무엇을 의미하는지 정의하고, 이전 값들과의 관계를 식으로 표현하면 코드는 자연스럽게 나온다.

dp[i] = i번째 피보나치 수
점화식: dp[i] = dp[i-1] + dp[i-2]

dp[i] = i번째 계단까지 오르는 경우의 수
점화식: dp[i] = dp[i-1] + dp[i-2]  (단, 조건에 따라 달라짐)

초기값(Base Case)을 빠뜨리지 마라

점화식은 이전 값에 의존하기 때문에 시작점이 없으면 계산이 안 된다.

dp[0] = 0;  // 빠뜨리면 틀린다
dp[1] = 1;

---

5. 코드

계단 오르기

한 번에 1칸 또는 2칸 오를 수 있을 때, n번째 계단까지 오르는 경우의 수

int climbStairs(int n) {
    if (n <= 2) return n;

    int[] dp = new int[n + 1];
    dp[1] = 1;
    dp[2] = 2;

    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

최솟값 구하기

동전으로 특정 금액을 만드는 최소 동전 개수

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 (i >= coin) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

---

6. 시간복잡도

방식	시간복잡도	공간복잡도
재귀 (DP 없음)	O(2^N)	O(N)
Top-Down (메모이제이션)	O(N)	O(N)
Bottom-Up (타뷸레이션)	O(N)	O(N)

DP를 쓰면 지수 시간이 선형 시간으로 줄어든다.

---

7. 주의사항

• 점화식 먼저, 코드는 나중이다. dp[i]의 정의를 명확히 하지 않으면 코드를 써도 뭘 하는지 모른다.
• 초기값을 꼭 설정해라. dp[0], dp[1]을 빠뜨리면 ArrayIndexOutOfBoundsException이나 틀린 답이 나온다.
• 배열 크기에 주의해라. dp[n]까지 필요하면 new int[n + 1]로 선언해야 한다.
• Bottom-Up이 스택 오버플로우에 안전하다. Top-Down은 재귀 깊이가 깊어지면 스택 오버플로우가 날 수 있다. n이 크면 Bottom-Up을 써라.