[알고리즘] 다이나믹 프로그래밍

다이나믹 프로그래밍(DP)란?

다이나믹 프로그래밍(DP, Dynamic Programming)은 문제를 해결하기 위한 하나의 접근 방식으로, 복잡한 문제를 더 작은 하위 문제로 나누어 해결하고 그 결과를 저장하여 반복적인 계산을 피하는 최적화 기법입니다. 주로 재귀적 또는 반복적 방식으로 문제를 해결하며, 이미 계산된 값을 재사용함으로써 중복 계산을 방지하는 것이 특징입니다.

다이나믹 프로그래밍(DP) 핵심 개념

• 재귀적 사고: 큰 문제를 더 작은 하위 문제로 나누고, 이미 해결된 작은 문제들이 있다는 믿음 아래 큰 문제를 해결합니다. 이때, 큰 문제와 작은 문제를 명확히 구분하는 것이 중요합니다. 작은 문제는 최소한의 정보만으로도 해결 가능한 문제를 의미하며, 이를 잘 구분해야 합니다.
• 불필요한 계산 제거: 동일한 하위 문제를 여러 번 계산하지 않기 위해 메모이제이션(Memoization) 기법을 사용합니다. 즉, 한 번 계산된 결과를 저장해 두고, 다시 계산이 필요할 때 저장된 값을 재사용하여 성능을 극대화합니다.
• 밑에서부터 계산하기: 문제를 해결할 때 꼭 재귀적 방식만 사용할 필요는 없습니다. 작은 문제부터 차례대로 해결해나가는 반복적 방식도 사용할 수 있습니다. 예를 들어, 팩토리얼을 계산할 때 가장 작은 값인 1부터 차례대로 계산해 나가듯, DP 문제에서도 하위 문제부터 차근차근 풀어나가는 방식이 효과적입니다.

다이나믹 프로그래밍(DP)로 풀 수 있는 대표적인 문제들

1. 피보나치 수열(Fibonacci Sequence):
   문제: n번째 피보나치 수를 구하는 문제
   설명: 이전 두 개의 피보나치 수를 이용해 n번째 피보나치 수를 계산합니다.

import java.util.HashMap;

public class Fibonacci {
    private static HashMap<Integer, Integer> memo = new HashMap<>();
    
    public static int fib(int n) {
        if (n <= 1) return n;
        if (memo.containsKey(n)) return memo.get(n);
        int result = fib(n - 1) + fib(n - 2);
        memo.put(n, result);
        return result;
    }
    
    public static void main(String[] args) {
        System.out.println(fib(10));  // Output: 55
    }
}

2. 최장 공통 부분 수열(Longest Common Subsequence, LCS):
   문제: 두 문자열의 최장 공통 부분 수열을 찾는 문제
   설명: 두 문자열 사이에서 순서를 유지하면서 가장 긴 공통 부분을 찾습니다.

public class LCS {
    public static int lcs(String s1, String s2) {
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];
        
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        return dp[s1.length()][s2.length()];
    }

    public static void main(String[] args) {
        System.out.println(lcs("ABCBDAB", "BDCAB"));  // Output: 4
    }
}

3. 최장 증가 부분 수열(Longest Increasing Subsequence, LIS):
   문제: 주어진 수열에서 가장 긴 증가하는 부분 수열을 찾는 문제
   설명: 수열에서 연속적으로 증가하는 부분을 찾아 그 길이를 구합니다.

import java.util.Arrays;

public class LIS {
    public static int lis(int[] arr) {
        int[] dp = new int[arr.length];
        Arrays.fill(dp, 1);
        
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        
        return Arrays.stream(dp).max().orElse(1);
    }

    public static void main(String[] args) {
        int[] arr = {10, 22, 9, 33, 21, 50, 41, 60, 80};
        System.out.println(lis(arr));  // Output: 6
    }
}

4. 배낭 문제(Knapsack Problem):
   문제: 제한된 무게를 가진 배낭에 최대 가치를 가지도록 물건들을 넣는 문제
   설명: 각 물건의 무게와 가치를 고려하여 최대 가치를 구합니다.

public class Knapsack {
    public static int knapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[][] dp = new int[n + 1][capacity + 1];
        
        for (int i = 1; i <= n; i++) {
            for (int w = 0; w <= capacity; w++) {
                if (weights[i - 1] <= w) {
                    dp[i][w] = Math.max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }
        
        return dp[n][capacity];
    }

    public static void main(String[] args) {
        int[] weights = {1, 3, 4, 5};
        int[] values = {1, 4, 5, 7};
        int capacity = 7;
        System.out.println(knapsack(weights, values, capacity));  // Output: 9
    }
}

5. 최소 편집 거리(Edit Distance, Levenshtein Distance):
   문제: 하나의 문자열을 다른 문자열로 변환하는데 필요한 최소 편집 작업(삽입, 삭제, 교체)의 수를 구하는 문제
   설명: 두 문자열을 비교하여 변환 비용을 최소화하는 방법을 찾습니다.

public class EditDistance {
    public static int editDistance(String s1, String s2) {
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];
        
        for (int i = 0; i <= s1.length(); i++) {
            for (int j = 0; j <= s2.length(); j++) {
                if (i == 0) {
                    dp[i][j] = j;
                } else if (j == 0) {
                    dp[i][j] = i;
                } else if (s1.charAt(i - 1) == s2.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[s1.length()][s2.length()];
    }

    public static void main(String[] args) {
        System.out.println(editDistance("kitten", "sitting"));  // Output: 3
    }
}

6. 동전 거스름돈 문제(Coin Change Problem):
   문제: 주어진 동전들로 특정 금액을 만드는 방법의 수를 구하거나 최소 동전 개수를 구하는 문제
   설명: 다양한 금액을 만들기 위해 가능한 동전 조합을 계산합니다.

public class CoinChange {
    public static 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];
    }

    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        int amount = 11;
        System.out.println(coinChange(coins, amount));  // Output: 3
    }
}

7. 최대 부분 배열 합(Maximum Subarray Sum, Kadane's Algorithm):
   문제: 주어진 배열에서 연속된 부분 배열의 합 중 가장 큰 값을 찾는 문제
   설명: 배열 내에서 가장 큰 합을 가지는 부분 배열을 찾습니다.

public class MaximumSubarraySum {
    public static int maxSubArray(int[] nums) {
        int maxSoFar = nums[0];
        int currentMax = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            currentMax = Math.max(nums[i], currentMax + nums[i]);
            maxSoFar = Math.max(maxSoFar, currentMax);
        }
        
        return maxSoFar;
    }

    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubArray(nums));  // Output: 6
    }
}

8. 최단 경로 찾기(Path Finding Problem, 다익스트라)
   문제: 주어진 그래프에서 특정 출발점에서 도착점까지의 최단 경로를 찾는 문제
   설명: 그래프에서 각 경로를 탐색하여 출발점에서 도착점까지의 최소 거리를 구합니다. 다익스트라(Dijkstra) 알고리즘이나 벨만-포드(Bellman-Ford) 알고리즘 같은 DP 기반의 최단 경로 알고리즘이 자주 사용됩니다.

import java.util.*;

public class Dijkstra {
    public static int[] dijkstra(int[][] graph, int src) {
        int n = graph.length;
        int[] dist = new int[n];
        boolean[] visited = new boolean[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.add(new int[]{src, 0});

        while (!pq.isEmpty()) {
            int[] node = pq.poll();
            int u = node[0];

            if (visited[u]) continue;
            visited[u] = true;

            for (int v = 0; v < n; v++) {
                if (graph[u][v] != 0 && !visited[v] && dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                    pq.add(new int[]{v, dist[v]});
                }
            }
        }

        return dist;
    }

    public static void main(String[] args) {
        int[][] graph = {
            {0, 10, 0, 30, 100},
            {10, 0, 50, 0, 0},
            {0, 50, 0, 20, 10},
            {30, 0, 20, 0, 60},
            {100, 0, 10, 60, 0}
        };
        int[] dist = dijkstra(graph, 0);
        System.out.println(Arrays.toString(dist));  // Output: [0, 10, 50, 30, 60]
    }
}