다이나믹 프로그래밍

다이나믹 프로그래밍이란?

다이나믹 프로그래밍은 복잡한 문제를 여러 하위 문제로 나누어 해결한 뒤, 그 결과를 결합하여 전체 문제를 해결하는 방법입니다. DP는 주로 중복된 하위 문제가 존재하는 경우에 사용됩니다. 같은 하위 문제를 여러 번 계산하지 않고, 이미 계산된 결과를 저장해두고 필요할 때 재사용하는 것이 핵심입니다.

---

다이나믹 프로그래밍의 특징

• 최적 부분 구조: 문제의 최적 해가 그 하위 문제들의 최적 해로 구성됩니다.
• 중복된 하위 문제: 동일한 하위 문제를 반복해서 계산하지 않고, 한 번 계산한 값을 저장해서 재사용합니다.

---

다이나믹 프로그래밍의 접근 방식 - Java 구현

상향식 접근 (Bottom-Up)

public class FibonacciDP {
    public static int fibonacci(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];
    }
 
    public static void main(String[] args) {
        int n = 10;
        System.out.println("Fibonacci " + n + "th number: " + fibonacci(n));
    }
}

        

        
      

이 코드에서는 피보나치 수열을 계산하기 위해 상향식 접근 방식을 사용했습니다. dp 배열에 작은 문제들의 결과를 저장하고, 이를 사용해 큰 문제를 해결합니다.

 

하향식 접근 (Top-Down)

public class FibonacciMemoization {
    private static int[] memo;
 
    public static int fibonacci(int n) {
        if (n <= 1) return n;
        if (memo[n] != -1) return memo[n];
 
        memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
        return memo[n];
    }
 
    public static void main(String[] args) {
        int n = 10;
        memo = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            memo[i] = -1;
        }
        System.out.println("Fibonacci " + n + "th number: " + fibonacci(n));
    }
}

        

        
      

이 코드에서는 재귀와 메모이제이션을 사용해 피보나치 수열을 계산했습니다. 처음 호출 시 memo 배열이 -1로 초기화되며, 이미 계산된 결과는 메모이제이션 배열에 저장됩니다. 이를 통해 중복 계산을 방지할 수 있습니다.

---

다이나믹 프로그래밍의 활용 사례

피보나치 수열: 앞서 설명한 대로, DP로 쉽게 해결할 수 있는 문제
최대 부분 배열 문제(Kadane's Algorithm): 주어진 배열에서 연속된 부분 배열 중 가장 큰 합을 찾는 문제
0/1 배낭 문제(Knapsack Problem): 제한된 무게를 초과하지 않으면서 최대 가치를 가지는 물건 조합을 찾는 문제
최단 경로 문제: 그래프에서 두 정점 사이의 최단 경로를 찾는 문제(Dijkstra, Floyd-Warshall 알고리즘)