DP란 ?

DP(다이나믹 프로그래밍)은 큰 문제를 작은 문제로 나누어 푼 후, 그 결과를 저장하여 같은 문제를 반복적으로 풀지 않도록 하는 알고리즘 기법이다.

DP의 핵심 개념

1. 중복된 계산을 줄이기 위해 결과를 저장 (Memoization)
2. 작은 문제들의 결과를 조합하여 큰 문제를 해결 (Optimal Substructure)
3. 점화식(Recurrence Relation)을 세워서 상태를 정의하고 채움

즉, 같은 계산을 여러 번 하지 않고, 한 번 계산한 값을 저장해서 빠르게 문제를 해결하는 방법

---

DP를 사용하는 이유

왜 필요할까 ?

일반적인 재귀(비효율적)

예를 들어 피보나치 수열을 재귀로 구현하면 다음과 같다.

public static int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

이렇게 하면 중복된 계산이 너무 많아져서 비효율적

• fibonacci(5)를 계산할 때 fibonacci(4), fibonacci(3)을 각각 호출해야 한다.
• $O(2^n)$의 시간이 걸려서 N이 커지면 연산량이 기하급수적으로 증가한다.

DP 방식(효율적)

한 번 계산한 값은 저장해서 다시 계산하지 않음!

public static int fibonacciDP(int n) {
    int[] dp = new int[n + 1]; // DP 테이블 생성
    dp[0] = 0; // 초기 값
    dp[1] = 1; // 초기 값
    
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]; // 점화식으로 테이블 채우기
    }
    return dp[n];
}

• 이렇게 하면 O(N) 만에 계산할 수 있다.
• 중복된 계산을 하지 않고, 저장된 값(dp 배열)을 사용해서 빠르게 계산

DP 테이블

DP 문제를 풀 땐, 작은 문제를 해결한 뒤 이 결과를 DP 테이블에 저장하고, 이를 활용해서 점점 큰 문제를 풀어나간다.

즉, DP 테이블의 목적은:

• 이미 계산된 결과를 저장해서 재사용
• 중복된 문제 해결을 방지해 효율성 향상
• 문제를 Bottom-up 방식

위 피보나치 수열을 예씨로 DP 테이블을 만들어보면 아래와 같다.

i	0	1	2	3	4	5
dp[i]	0	1	1	2	3	5

dp배열이 바로 DP 테이블이 되는 것인데,
예를 들어서,

• dp[4]를 계산할 때 이미 저장된 dp[3]과 dp[2]를 더해서 빠르게 구할 수 있다.
• 이를 통해 매번 재귀 호출로 계산하지 않아도 돼서 속도가 훨씬 빨라진다.

DP 테이블 사용 방법 정리

1. DP 테이블 정의하기(무엇을 저장할지)

• ex) dp[i] = "피보나치 수열의 i번째 항의 값"
  

2. 초기 값 설정하기 (Base Case)

• ex) dp[0] = 0, dp[1] = 1

3. 점화식으로 DP 테이블 채우기

• ex) dp[i] = dp[i - 1] + dp[i - 2]

---

DP를 적용할 수 있는 조건

1. 최적 부분 구조 (Optimal Substructure)

• 큰 문제를 작은 문제로 나누어 풀 수 있어야 한다.
• 예 : fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)

2. 중복되는 부분 문제 (Overlapping Subproblems)

• 같은 계산이 반복적으로 일어나야 한다.
• 예: 피보나치 수열 fibonacci(3), fibonacci(2) 같은 값이 여러 번 계산됨.

이 두 조건이 만족되면 DP를 사용할 수 있다.

DP의 구현 방식

방식	설명
1. Top-Down (메모이제이션)	재귀 + 메모이제이션을 통해 큰 문제에서 작은 문제로 접근
2. Bottom-Up (반복문)	반복문을 사용하여 작은 문제에서 큰 문제로 해결

장단점

방식	특징	장점	단점
Top-Down (재귀 + 메모이제이션)	큰 문제 -> 작은 문제	필요한 부분만 계산(연산 절약 가능), 코드가 직관적	재귀 호출 많으면 스택 오버플로우 위험, 실행 속도가 느릴 수 있음
Bottom-Up (반복문)	작은 문제-> 큰 문제	스택 오버플로우 없음, 실행 속도 빠름	모든 부분을 계산해야 해서 불필요한 계산 가능

Top-Down

public class FibonacciTopDown {
    static int[] dp = new int[100];  // DP 배열

    public static int fibonacci(int n) {
        if (n <= 1) return n;
        if (dp[n] != 0) return dp[n];  // 이미 계산한 값이면 저장된 값 반환
        return dp[n] = fibonacci(n - 1) + fibonacci(n - 2);
    }

    public static void main(String[] args) {
        System.out.println(fibonacci(10));  // 출력: 55
    }
}

• 재귀를 사용하지만, 이미 계산된 값은 다시 계산하지 않음
• 하지만 재귀 호출이 많으면 스택 오버플로우 위험

Bottom-Up

public class FibonacciBottomUp {
    public static int fibonacci(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];
    }

    public static void main(String[] args) {
        System.out.println(fibonacci(10));  // 출력: 55
    }
}

• 반복문을 사용해서 더 안정적으로 동작
• Top-Down 방식보다 실행 속도가 빠를 수도 있음

---

DP는 언제 사용할까 ?

문제 유형	DP 가능 여부	사용 예시
피보나치 수열	가능	점화식 적용 가능
배낭 문제	가능	최적 부분 구조 있음
LIS(최장 증가 부분 수열)	가능	작은 문제 조합 가능
이진 탐색	불가능	중복 계산 X
정렬(퀵정렬, 병합정렬)	불가능	DP 필요 없음

• 점화식으로 표현 가능하고, 중복 계산이 많다면 DP 고려
• "최적 부분 구조" + "중복되는 부분 문제" -> DP를 사용할 수 있는 핵심 조건

---

결론

• DP는 중복 계산을 피하고 효율성을 높이는 기법이다.
• 재귀로 간편한 Top-Down과, 반복문으로 빠르고 안정적인 Bottom-Up 방식이 있다.
• DP를 사용하려면 반드시 "최적 부분 구조"와 "중복되는 부분 문제"를 만족해야 한다.
• 입력의 크기가 크거나 안정성이 중요하다면 Bottom-Up 방식이 더 적합하다.

---

DP 문제

백준 1495

https://www.acmicpc.net/problem/1495

package week2;

import java.io.*;
import java.util.*;


public class Problem1495{
    
    static boolean[][] dp;
    static int N; //곡 개수
    static int S; // 시작 볼륨
    static int M; // 최대 볼륨
    static int[] V; //볼륨 변화량량

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        V = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            V[i] = Integer.parseInt(st.nextToken());
        }

        maxVolume(N);

    }

    private static void maxVolume(int N) {
        dp = new boolean[N+1][M+1];
        dp[0][S] = true;    
        
        for(int i = 0; i < N; i++) {
            for(int j = 0; j <= M; j++) {
                if(dp[i][j]){
                    if(j + V[i] <= M)
                        dp[i+1][j+V[i]] = true;
                    if(j - V[i] >= 0)
                        dp[i+1][j-V[i]] = true;
                }
            }
        }

        int maxVolume = -1;
        for(int j =0; j <= M; j++) {
            if(dp[N][j])
                maxVolume = j;
        }

        System.out.println(maxVolume);
    }
}