다이나믹 프로그래밍

DP(Dynamic Programming)

중복되는 연산을 줄이는 방식
문제를 작은 하위 문제로 나누어 해결한 결과를 저장해 두었다가, 동일한 하위 문제가 다시 나타날 때 이를 재사용하는 방식

다이나믹 프로그래밍의 기본 원리

중복된 하위 문제:
- 문제를 작은 하위 문제로 나누었을 때, 동일한 하위 문제가 여러 번 반복해서 나타나는 경우.
- 예를 들어, 피보나치 수열 계산에서는 F(n) = F(n-1) + F(n-2)와 같은 형태로, 동일한 계산이 반복된다.
최적 부분 구조:
- 문제의 최적해가 하위 문제들의 최적해로 구성될 수 있는 경우.
- 예를 들어, 최단 경로 문제에서는 전체 경로의 최적해가 부분 경로의 최적해들로 구성된다.

다이나믹 프로그래밍의 두 가지 접근법

1. 탑다운(Top-Down) 접근법 (메모이제이션)

재귀 호출을 통해 문제를 하위 문제로 나누고, 이미 계산된 하위 문제의 결과를 저장하여 중복 계산을 방지
일반적으로 재귀와 메모이제이션(결과 저장) 기법을 사용

// 메모이제이션을 이용한 피보나치 수열
public class Fibonacci {
    private static Map<Integer, Long> memo = new HashMap<>();

    public static long fib(int n) {
        if (n <= 1) return n;
        if (memo.containsKey(n)) return memo.get(n);

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

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

2. 바텀업(Bottom-Up) 접근법 (반복문)

// 바텀업을 이용한 피보나치 수열
public class Fibonacci {
    public static long fib(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 - 1] + dp[i - 2];
        }

        return dp[n];
    }

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

다이나믹 프로그래밍의 예시 문제

피보나치 수열
- 문제: F(n) = F(n-1) + F(n-2), F(0) = 0, F(1) = 1
- 중복된 하위 문제와 최적 부분 구조를 가지며, DP로 해결 가능
최단 경로 문제
- 예를 들어, 그래프에서 두 점 사이의 최단 경로를 찾는 문제 (다익스트라 알고리즘, 벨만-포드 알고리즘)
배낭 문제(Knapsack Problem)
- 문제: 제한된 무게 내에서 가치가 최대가 되도록 물건을 선택하는 문제
- DP를 통해 하위 문제를 해결하며 최적해를 찾음
최장 공통 부분 수열(Longest Common Subsequence)
- 문제: 두 문자열에서 공통된 부분 문자열 중 가장 긴 것을 찾는 문제
- DP를 통해 부분 문제를 해결하며 전체 문제를 해결

다이나믹 프로그래밍의 장점과 단점

장점
- 중복 계산을 피할 수 있어 시간 복잡도를 크게 줄일 수 있음
- 다양한 최적화 문제를 효율적으로 해결할 수 있음
단점
- 문제에 따라 추가적인 메모리 사용이 필요할 수 있음
- 문제를 DP로 변환하는 과정이 복잡할 수 있음