다이나믹 프로그래밍(Dynamic Programming)

1. DP(Dynamic Programming)이란?

- 다이나믹 프로그래밍은 복잡한 문제를 더 작은 하위 문제로 나누어 해결하고 그 결과를 중복해서 다시 계산하지 않도록 저장하거나 차례차례 결과를 쌓아올리는 기법이다.

- 분할정복과 비슷하지만 하위 문제가 중복되어 등장할 때 중복 계산을 제거하는것이 차이점이다.

 

1-1. 핵심 아이디어

- 중복 부분 문제(Overlapping Subproblems): 동일한 하위 문제가 여러 번 등장하면 한 번 계산한 값을 저장해놨다가 재사용

- 최적 부분 구조(Optimal Substructure): 문제의 최적 해가 하위 문제의 최적해들로 만들어져야 함

 

1-2. 장단점

- 장점: 중복 계산을 제거하여 시간복잡도가 감소, 단계별 구현 패턴이 일정

- 단점: 상태 저장용 메모리(배열, 맵 등) 필요, 점화식 설계에 난이도가 있음

 

2. 구현 방식

2-1. Top Down(메모이제이션)

- 재귀를 호출하면서 결과를 맵이나 배열에 저장

- 코드 구조가 직관적이다.

// 피보나치 예제(Top Down)

public class FiboTopDown {

    static Map<Integer, Long> memo = new HashMap<>();

    public static long fibo(int n) {
        if(n <= 1) {
            return n;
        }

        if(memo.containsKey(n)) {
            return memo.get(n);
        }

        long res = fibo(n-1) + fibo(n-2);
        memo.put(n, res);
        return res;
    }

    public static void main(String[] args) {
        // 출력: 12586269025
        System.out.println(fibo(50));
    }
}

 

 

2-2. BottomUp(타뷸레이션)

- 작은 하위문제부터 반복문으로 차례차례 결과 채우기

- 스택 오버플로우 걱정 없고 공각 최적화 기법을 적용하기 쉽다

// 피보나치 예제(Bottom Up

public class FiboBottomUp {
    public static long fibo(int n) {
        if(n <= 1) {
            return n;
        }

        long[] dp = new long[n+1];
        dp[0] = 0;
        dp[1] = 1;

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

    public static void main(String[] args) {
        // 출력: 12586269025
        System.out.println(fib(50));
    }
}

 

3. DP 활용 문제

3-1. 계단오르기

- 한 계단에 1칸 또는 2칸씩 오를 수 있을 때 n개의 계단을 오르는 방법의 수

- 점화식: dp[i] = dp[i-1] + dp[i-2]

public class ClimbStairs {
    public static int climb(int n) {
        if(n <= 1) {
            return 1;
        }

        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) {
        // 출력: 8
        System.out.println(climb(5));
    }
}

 

3-2. 동전 교환

- 다양한 동전이 주어질 때 합이 target이 되도록 만드는 모든 경우의 수

- 점화식: for each coin c: dp[i] += dp[i-c];

public class CoinChargeCount {
    public static int cointCharge(int[] coins, int target) {
        int[] dp = new int[target+1];
        dp[0] = 1;

        for(int c : coins) {
            for (int i = c; i <= target; i++) {
                dp[i] += dp[i-c];
            }
        }

        return dp[target];
    }

    public static void main(String[] args) {
        // 예제 데이터
        int[] coins = {1, 2, 5};

        // 출력: 11
        System.out.println(coinChange(coins, 11));
    }
}