contents

📘 코딩 테스트를 위한 동적 프로그래밍(DP) 가이드

다음은 DP의 핵심 개념, 유형, 구현 전략, 그리고 Java 스타일의 예제 코드를 포함한 상세 설명입니다.

1. 동적 프로그래밍(DP)이란?

동적 프로그래밍(Dynamic Programming)은 큰 문제를 작은 하위 문제로 나누고, 그 결과를 저장하여 재사용함으로써 불필요한 중복 계산을 피하고 효율적으로 문제를 해결하는 방법입니다.

• 핵심 아이디어:
  • 중복되는 하위 문제(Overlapping Subproblems)
  • 최적 부분 구조(Optimal Substructure)
• 종류:
  1. Top-down (메모이제이션): 재귀 + 캐싱
  2. Bottom-up (탭메이제이션): 반복문으로 dp 테이블 채우기
• 완전 탐색이 지수 시간복잡도를 가지는 경우에도 DP를 사용하면 다항 시간으로 줄일 수 있습니다.

2. DP 패턴 & 예제

a. 피보나치 수열

재귀 (비효율적)

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

DP (Top-down + 메모이제이션)

int[] memo = new int[n+1];
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);
}

DP (Bottom-up)

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];
}

b. 0/1 배낭 문제 (Knapsack)

문제:
각기 다른 무게와 가치를 가진 n개의 아이템이 주어질 때, 배낭 무게 제한 W 안에서 최대 가치를 구하세요.

int knapsackDP(int[] w, int[] v, int W) {
    int n = w.length;
    int[][] dp = new int[n+1][W+1];
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= W; j++) {
            if (w[i-1] <= j)
                dp[i][j] = Math.max(dp[i-1][j],
                                    dp[i-1][j-w[i-1]] + v[i-1]);
            else
                dp[i][j] = dp[i-1][j];
        }
    }
    return dp[n][W];
}

• dp[i][j]: 처음 i개의 아이템을 고려했을 때, 무게 한도 j에서의 최대 가치

c. 최장 증가 부분수열 (LIS)

int lengthOfLIS(int[] nums) {
    int n = nums.length, max = 1;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    for (int i = 1; i < n; i++)
        for (int j = 0; j < i; j++)
            if (nums[i] > nums[j])
                dp[i] = Math.max(dp[i], dp[j] + 1);
    for (int val : dp) max = Math.max(max, val);
    return max;
}

• dp[i]: i번째 원소로 끝나는 LIS의 길이

d. 편집 거리(Edit Distance)

int editDistance(String a, String b) {
    int[][] dp = new int[a.length()+1][b.length()+1];
    for (int i = 0; i <= a.length(); i++)
        for (int j = 0; j <= b.length(); j++) {
            if (i == 0) dp[i][j] = j;
            else if (j == 0) dp[i][j] = i;
            else if (a.charAt(i-1) == b.charAt(j-1))
                dp[i][j] = dp[i-1][j-1];
            else
                dp[i][j] = 1 + Math.min(dp[i-1][j-1],
                               Math.min(dp[i-1][j], dp[i][j-1]));
        }
    return dp[a.length()][b.length()];
}

• dp[i][j]: a의 처음 i개 문자를 b의 처음 j개 문자로 바꾸는데 필요한 최소 연산 수

e. 동전 교환 (Coin Change)

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

• dp[i]: i원을 만들기 위해 필요한 최소 동전 개수

3. DP 문제 유형별 분류

4. DP 구현 단계

1. 상태 정의 (State)
   • 문제를 더 작은 하위 문제로 정의
2. 기저 조건 (Base case)
   • 가장 작은 값의 해를 미리 정의
3. 점화식 (Recurrence Relation)
   • 큰 문제를 작은 문제의 해로부터 만드는 방법
4. 계산 순서 (Iteration Order)
   • Bottom-up 또는 Top-down
5. 최적화 (Optimization)
   • 공간 최적화(1D 배열), 불필요한 계산 줄이기

5. 실전 팁

• 문제에서 "최대", "최소", "경우의 수" 등이 나오면 DP를 의심
• Top-down: 작성하기 쉬움, 이해 직관적
  Bottom-up: 메모리 예측 가능, 반복문
• dp 테이블 상태를 출력해서 디버깅
• 문자열/격자: 2D 배열, 수열/숫자: 1D 배열 많이 사용

6. 고급 개념

• 상태 압축(State Compression): 비트마스크 등을 사용해 공간 절약
• 다차원 DP: dp[i][j][k]… 형태, 제약 조건 추가
• 트리/그래프 DP: DFS + DP 결합
• DP + 백트래킹: 최적해 뿐 아니라 해의 목록도 생성

7. 요약 테이블

references