[코드트리] 동적계획법(DP) 쉽게 이해하기 (점화식부터 구현까지 총정리)

목차

1. 청약 통장 6회차 : 나만의 알고리즘 개념서 만들기

1-1. 6회차 미션

• 미션: 나만의 방식으로 알고리즘 개념 설명하기
• 가장 자신 있거나 좋아하는 유형을 하나 골라, 다른 사람에게 설명하는 나만의 개념서를 작성한다.
• 쉬운 설명 + 코드트리 문제 풀이 과정 + 자주 하는 실수/꿀팁을 함께 담는다.

▲ 코드트리 - 6회차 납입 가이드

1-2. 주제 선정 이유

• DP는 여러 문제에서 자주 만나본 유형이고, 점화식을 세워 푸는 과정 자체가 재밌어서 골랐다.
• 다만 최근 갭체크에서는 DP가 🟡 불안정한 지식으로 분류되어, 좋아하는 것과 별개로 손에 완전히 익지는 않은 상태였다.
• 이번 개념서를 쓰며 점화식 감각을 확실히 다지기로 했다.

2. 동적계획법(DP)이란

2-1. 개념 정의

• 동적계획법(Dynamic Programming) : 큰 문제를 같은 모양의 더 작은 문제로 쪼개 먼저 풀고, 그 결과를 모아 큰 문제를 해결하는 기법
• 점화식(recurrence) : 작은 문제의 답으로 큰 문제의 답을 표현한 식
• 초기조건(base case) : 더 쪼갤 수 없는 가장 작은 문제의 정답

▲ 코드트리 - 동적계획법

2-2. 점화식

• 코드트리에서는 1부터 N까지의 곱을 예시로 든다. F(N)을 1부터 N까지의 곱이라 정의하면 식은 다음과 같다.

- F(N) = F(N-1) × N (N > 1) : 점화식
- F(1) = 1 : 초기조건

• 큰 문제 F(5)는 F(4)를, F(4)는 F(3)을... 이런 식으로 한 칸씩 작은 문제로 내려가다 초기조건 F(1)=1에서 멈춘다.
• 거꾸로 F(1)부터 답을 모아 올라오면 F(5) = 1×2×3×4×5 = 120이 된다.

▲ 점화식 개념도

3. Bottom-up vs Top-down

같은 점화식이라도 코드로 옮기는 방법은 크게 두 가지로 나뉜다. 방향만 반대일 뿐 동일하다.

3-1. Bottom-up : 반복문으로 표 채우기

• 초기조건 F[1]을 먼저 채워두고, 작은 인덱스부터 큰 인덱스로 표를 채워 나가는 방식이다.
• F[i]를 구할 때 F[i-1]이 이미 채워져 있다.

F = [0] * (n + 1)            # 결과를 저장할 표
F[1] = 1                     # 초기조건 먼저 채우기
for i in range(2, n + 1):    # 작은 값부터 차례대로
    F[i] = F[i - 1] * i      # 점화식을 그대로 옮김
print(F[n])                  # 큰 문제의 답

▲ Bottom-up 표 채우기

3-2. Top-down : 재귀와 메모이제이션

• 큰 문제를 함수로 호출하면, 함수가 알아서 작은 문제를 다시 호출하며 내려가는 방식이다.
• 종료조건 자리에 초기조건을 넣고, 나머지는 점화식을 그대로 적으면 된다.

def f(n):
    if n == 1:          # 종료조건 = 초기조건
        return 1
    return f(n - 1) * n  # 점화식

• 그런데 재귀를 그대로 쓰면 함정이 있다. 피보나치처럼 같은 작은 문제가 여러 번 호출되면 계산이 기하급수적으로 늘어난다.
• 이때 한 번 구한 답을 배열에 저장(메모이제이션)해 두면, 같은 호출은 즉시 재사용해 중복을 없앤다.

▲ 재귀 호출 트리와 메모이제이션

3-3. 두 방식 비교

구분	Bottom-up (반복문)	Top-down (재귀 + 메모)
방향	작은 문제 → 큰 문제	큰 문제 → 작은 문제
구현	for / while 반복문	재귀 호출
장점	스택 오버플로 걱정이 없고 빠르다	점화식과 코드가 1:1로 닮아 직관적이다
주의	채우는 순서를 직접 설계해야 한다	메모이제이션이 없으면 시간 초과가 난다

4. 코드트리 문제에 적용하기 : 사각형 채우기 3

▲ 코드트리 - 사각형 채우기 3

4-1. 문제 이해

• 문제 : 2×N 사각형을 1×2, 2×1, 1×1 타일로 빈틈없이 채우는 방법의 수를 구한다.
• 예제 : N=1 → 2가지, N=2 → 7가지, N=3 → 22가지.
• 작은 N의 답으로 큰 N의 답을 만드는 전형적인 DP 문제다.

4-2. 점화식 세우기

• dp[n]을 "2×n 사각형을 채우는 방법의 수"로 정의하면, 점화식은 다음과 같다.

- dp[n] = 3 × dp[n-1] + dp[n-2] - dp[n-3] (n ≥ 3) : 점화식
- dp[0] = 1, dp[1] = 2, dp[2] = 7 : 초기조건

• 제대로 세웠는지 작은 N으로 검증한다. dp[3] = 3×7 + 2 - 1 = 22로 예제와 일치한다.
• 한 칸 더 확인하면 dp[4] = 3×22 + 7 - 2 = 71이다.
• 정확한 유도는 각 열에서 다음 열로 '튀어나온 칸'의 상태까지 추적해야 하지만, 이렇게 작은 N으로 식이 맞는지 검증하는 게 가장 빠르다.

4-3. 의사코드

1. dp[0]=1, dp[1]=2, dp[2]=7로 초기화한다.
2. i를 3부터 N까지 키우며 dp[i] = 3×dp[i-1] + dp[i-2] - dp[i-3]을 채운다.
3. dp[N]을 출력한다.

4-4. 구현 코드 (Java)

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
 
        long MOD = 1_000_000_007; 
        
        // dp[i] = 2×i 사각형을 채우는 방법의 수
        long[] dp = new long[Math.max(n + 1, 3)];
        dp[0] = 1;   // 빈 사각형: 1가지
        dp[1] = 2;
        dp[2] = 7;
 
        for (int i = 3; i <= n; i++) {
            dp[i] = (3 * dp[i - 1] + dp[i - 2] - dp[i - 3]) % MOD;

            if (dp[i] < 0) {
                dp[i] += MOD;
            }
        }
 
        System.out.println(dp[n]);
    }
}

• 이 문제는 Bottom-up으로 풀었다.
• N이 커지면 경우의 수가 빠르게 늘어나므로, 자바에서는 결과 자료형을 long으로 두는 게 안전하다. (파이썬은 큰 수를 자동 처리한다.)
• 뺄셈 때문에 음수가 나올 수 있으니 dp[i] = ((식) % MOD + MOD) % MOD 형태로 보정한다.

📎 코드트리 트레일 둘러보러 가기

5. 자주 하는 실수

• 초기조건을 빠뜨린다. 점화식만 적고 base case를 안 넣으면 재귀가 끝나지 않거나 표가 비어버린다. 점화식보다 초기조건을 먼저 적는 습관이 안전하다.
• 점화식의 방향을 헷갈린다. F[i]가 F[i-1]에 의존하면, 반복문은 반드시 작은 i부터 채워야 한다. 순서가 꼬이면 아직 비어 있는 칸을 참조하게 된다.
• 재귀에 메모이제이션을 안 붙인다. 점화식이 맞아도 중복 호출 때문에 시간 초과가 난다. 재귀 DP에는 메모 배열이 필수다.
• 배열 인덱스 범위를 놓친다. 크기를 n+1로 잡고 1번 인덱스부터 쓰면 off-by-one 실수를 줄일 수 있다.

나만의 DP 풀이 순서
- 1단계: 상태(무엇을 dp[i]로 둘지)를 한 문장으로 정의한다.
- 2단계: dp[i]를 더 작은 항으로 표현하는 점화식을 세운다.
- 3단계: 초기조건을 정한다.
- 4단계: 반복문 또는 재귀+메모 중 편한 쪽으로 옮긴다.

6. 마무리

• 예전에는 DP를 보면 점화식을 어떻게 세울지 막막했는데, 상태 정의 → 점화식 → 초기조건이라는 순서를 정해두니 편했다.
• 특히 Bottom-up과 Top-down이 결국 같은 점화식의 방향만 다른 것이라는 점을 그림으로 그려보고 나서 머릿속에서 두 방식이 정리되었다.
• 갭체크에서 불안정하게 떴던 DP를 직접 설명해보니, 남에게 설명할 수 있을 때 비로소 내 것이 된다는 걸 다시 느꼈다.