다이나믹 프로그래밍

큰 문제를 작은 문제로 나누어 해결하고, 이를 저장하여 중복 계산을 방지하는 알고리즘 기법
일반적으로 최적 부분 구조, 중복 부분 문제를 만족하는 문제에서 사용

• 최적 부분 구조 : 문제의 최적 해가 부분 문제들의 최적 해로 구성될 수 있음
• 중복 부분 문제 : 동일한 작은 문제들이 반복해서 계산됨

해결 방식

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

• 재귀 + 캐싱 활용
• 큰 문제를 작은 문제로 쪼개어 해결
• 계산한 결과를 저장하여 동일한 연산을 반복하지 않음
• 보통 DP 배열을 선언하고, 재귀 호출 전에 이미 계산된 값인지 확인

2. Bottom-Up(반복문, Tabulation)

• 작은 문제를 먼저 해결한 후, 이를 조합해 큰 문제를 해결
• 보통 DP 배열을 만들어 순차적으로 채워감
• 재귀 호출이 없어 함수 호출 스택 오버헤드가 줄어듦
• 공간 최적화가 가능(배열 없이 변수만으로 해결 가능)

대표적인 문제

1. 파보나치 수열 -> Top-Down 방식

   파보나치 수열은 이전 두 항의 합으로 이루어지는 수열

public class FibonacciTopDown{
	static Map<Integer, Integer> memo = new HashMap<>();
    
    public static int fibonacci(int n){
    	if(n <= 1) return n;
        if(memo.containsKey(n)) return memo.get(n);
        
        int result = fibonacci(n - 1) + fibonacci(n - 2);
        memo.put(n, result);
        return result;
    }
    
    public static void main(String[] args){
    	System.out.println(fibonacci(10));
    }
}

2. 배낭 문제 -> Bottom-Up 방식

   주어진 가방의 용량에 최대한 가치가 높은 물건을 넣는 문제

public class KnapsackBottomUp{
    public static int knapsack(int W, int[] weights, int[] values, int n){
    	int[][] dp = new int[n + 1][w + 1];
        
        for(int i = 1; i <= n; i++){
        	for(int w = 0; w <= W; 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][w];
    }
    
    public static void main(String[] args){
    	int[] values = {60, 100, 120};
        int[] weights = {10, 20, 30};
        int W = 50;
        itn n = values.length;
        
        System.out.println(knapsack(W, weights, values, n));
    }
}

3. 최장 증가 부분 수열 > Bottom-Up 방식

   주어진 수열에서 순서를 유지하면서 가장 긴 부분 수열을 찾는 문제

public class LISBottomUp{
    public static int longestIncreasingSubsequence(int[] nums){
    	int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        
        int maxLength = 1;
        for(int i = 1; i < n; i++){
        	for(int j = 0; j < i; j++){
            	if(nums[i] > nums[j]){
                	dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLength = Math.max(maxLength, dp[i]);
        }
        
        return maxLength;
    }
    
    public static void main(String[] args){
    	int[] nums = {10, 22, 9, 33, 21, 50, 41, 60);
        System.out.println(longestIncreasingSubsequence(nums));
    }
}

4. 최단 경로 문제 > Bottom-Up 방식

   주어진 그래프에서 시작 노드부터 도착 노드까지의 최단 경로를 찾는 문제

class DijkstraBottomUp {
    static class Node implements Comparable<Node> {
        int vertex, cost;
        Node(int vertex, int cost) {
            this.vertex = vertex;
            this.cost = cost;
        }
        public int compareTo(Node other) {
            return this.cost - other.cost;
        }
    }

    public static int[] dijkstra(int V, List<List<Node>> graph, int start) {
        int[] dist = new int[V];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));

        while (!pq.isEmpty()) {
            Node current = pq.poll();
            int u = current.vertex;

            for (Node neighbor : graph.get(u)) {
                int v = neighbor.vertex;
                int weight = neighbor.cost;

                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.add(new Node(v, dist[v]));
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        int V = 5;
        List<List<Node>> graph = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            graph.add(new ArrayList<>());
        }

        graph.get(0).add(new Node(1, 10));
        graph.get(0).add(new Node(4, 3));
        graph.get(1).add(new Node(2, 2));
        graph.get(2).add(new Node(3, 1));
        graph.get(4).add(new Node(1, 4));
        graph.get(4).add(new Node(2, 8));

        int[] distances = dijkstra(V, graph, 0);
        System.out.println(Arrays.toString(distances)); // [0, 7, 10, 11, 3]
    }
}

5. 문자열 편집 거리 문제 > Bottom-Up 방식

   두 문자열 사이의 최소 편집 거리를 찾는 문제

public class EditDistanceBottomUp {
    public static int editDistance(String str1, String str2) {
        int m = str1.length(), n = str2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0) {
                    dp[i][j] = j; // 삭제만 가능
                } else if (j == 0) {
                    dp[i][j] = i; // 삽입만 가능
                } else if (str1.charAt(i - 1) == str2.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[m][n];
    }

    public static void main(String[] args) {
        String str1 = "horse";
        String str2 = "ros";
        System.out.println(editDistance(str1, str2)); // 3
    }
}

장단점

장점

• 중복 계산을 줄일 수 있다.
• 효율적인 시간 복잡도를 가질 수 있다.
  단점
• 메모리 사용량이 크다.