DP개념과 구현 방법

목차

• 1. DP란 무엇인가?
• 2. 언제 DP를 써야 할까? (핵심 조건 2가지)
• 3. 구현의 두 가지 스타일: Top-Down vs Bottom-Up
• 4. DP 문제 풀이 3단계 루틴

코딩 테스트의 ‘최종 보스’로 불리는 다이나믹 프로그래밍(Dynamic Programming, 동적 계획법). 이름만 들으면 뭔가 역동적이고 어려워 보이지만, 사실 “기억력 좋은 알고리즘”이라고 부르는 게 더 정확합니다. 오늘은 중학생도 이해할 수 있도록, DP의 개념부터 코드 구현까지 아주 쉽게 파헤쳐 보겠습니다.

1. DP란 무엇인가?

DP의 핵심은 “한 번 푼 문제는 답을 적어두고, 다시 풀지 않는다”는 것입니다.

여러분이 수학 시험을 보는데, 15 + 15라는 계산 문제가 1번에도 나오고, 5번에도 나오고, 10번에도 나온다고 상상해 보세요. 미련한 방법은 문제가 나올 때마다 덧셈을 다시 하는 겁니다.

하지만 스마트한 방법(DP)은 1번에서 답이 30인 걸 구했으니, 5번과 10번 문제에서는 계산 없이 바로 30을 적어내는 것이죠. 컴퓨터 과학에서는 이렇게 답을 어딘가에 적어두는 행위를 메모이제이션(Memoization)이라고 부릅니다. 이 작은 차이가 엄청난 속도의 차이를 만듭니다.

2. 언제 DP를 써야 할까? (핵심 조건 2가지)

모든 문제에 기억력을 쓸 수는 없습니다. DP가 힘을 발휘하려면 다음 두 가지 조건이 맞아야 합니다.

• 큰 문제를 작은 문제로 나눌 수 있다 (Optimal Substructure): 예를 들어 ’10층까지 가는 방법’은 ‘9층에서 한 칸 오르기’와 ‘8층에서 두 칸 오르기’로 쪼개서 생각할 수 있어야 합니다.
• 똑같은 작은 문제가 반복된다 (Overlapping Subproblems): 피보나치 수열처럼 f(3)을 구하는 과정이 f(4)를 구할 때도, f(5)를 구할 때도 계속 필요해야 합니다.

(피보나치 수열 계산 시 동일한 하위 문제(f(3), f(2) 등)가 반복해서 호출되는 구조)

3. 구현의 두 가지 스타일: Top-Down vs Bottom-Up

DP를 코드로 옮기는 방법은 크게 두 가지입니다. 상황에 따라 편한 것을 쓰면 되지만, 보통 Bottom-Up(반복문) 방식이 성능상 조금 더 유리하고 많이 쓰입니다.

① Top-Down (하향식) – 재귀 + 메모장

“큰 문제를 풀다가 막히면 작은 문제를 푼다”는 방식입니다. 주로 재귀 함수를 사용하며, 코드가 점화식과 똑같이 생겨서 직관적입니다.

// 메모장(Memoization) 배열 초기화 필요 (보통 -1이나 0으로 초기화)
static int[] memo = new int[1001]; 

public int topDown(int n) {
    // 1. 기저 조건 (종료 조건)
    if (n <= 1) return n;
    
    // 2. 이미 계산한 적이 있다면 메모장에서 꺼내 씀 (핵심!)
    if (memo[n] != 0) return memo[n]; 

    // 3. 점화식 계산 후 메모장에 적어둠
    memo[n] = topDown(n - 1) + topDown(n - 2);
    return memo[n];
}

② Bottom-Up (상향식) - 반복문

"작은 문제부터 차곡차곡 답을 채워 큰 문제를 푼다"는 방식입니다. 주로 반복문(for)을 사용하며, 함수 호출 오버헤드가 없어 효율적입니다. 이를 타블레이션(Tabulation)이라고도 합니다.

public int bottomUp(int n) {
    int[] dp = new int[n + 1];

    // 1. 초기값 설정 (가장 작은 문제의 답)
    dp[1] = 1;
    dp[2] = 2;

    // 2. 작은 문제 -> 큰 문제 순서로 채우기
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n]; // n번째 문제의 정답 반환
}

4. DP 문제 풀이 3단계 루틴

DP 문제를 만나면 당황하지 말고 딱 3단계만 기억하세요.

1. 테이블 정의하기: dp[i]가 무엇을 의미하는지 한 문장으로 정의합니다.
   (예: dp[i] = i번째 계단까지 오르는 경우의 수)
2. 점화식 찾기 (가장 중요): 현재 상태(dp[i])를 구하기 위해 이전 단계(dp[i-1], dp[i-2])를 어떻게 활용할지 식을 세웁니다.
   (예: dp[i] = dp[i-1] + dp[i-2])
3. 초기값(Base Case) 설정하기: 점화식은 이전 값을 참조하므로, 가장 앞부분(dp[0], dp[1])은 직접 값을 넣어줘야 합니다.
   (예: dp[1] = 1, dp[2] = 2)

다음 2부에서는 실제 코딩 테스트에 자주 나오는 [DP 5대 필수 유형과 문제 판별법]에 대해 자세히 알아보겠습니다.