동적 프로그래밍의 세 가지 방법: 📈📉💾

동적 프로그래밍은 복잡한 문제를 해결하기 위한 알고리즘입니다. 큰 문제를 작은 문제로 분해하고, 이 작은 문제들의 해를 저장하여 중복된 계산을 피합니다. 이 글에서는 자바 언어를 사용하여 동적 프로그래밍의 세 가지 방법인 상향식(📈), 하향식(📉), 그리고 **메모이제이션(💾)**에 대해 설명하겠습니다. 이러한 방법들은 배낭 문제 🎒, 최단 경로 문제🚶‍♂️, 문자열 매칭 문제🔗 등 다양한 문제에서 활용됩니다. 각 방법의 원리, 시간 복잡도⏱️ 및 공간 복잡도💾를 예제와 함께 살펴보겠습니다.

1. 하향식(📉 재귀 + 메모이제이션 💾)

하향식 방법은 재귀🔄 방식으로 작동합니다. 주어진 문제를 더 작은 문제들로 분해하며, 가장 간단한 문제까지 도달하게 됩니다. 중복 계산을 피하기 위해 메모이제이션 💾을 사용하여 중간 결과를 저장합니다. 이 방법은 특히 문제 자체가 재귀 구조를 가지고 있을 때 직관적으로 이해하기 쉽습니다. 하지만 깊은 재귀 호출로 인한 스택 오버플로우 문제가 발생할 수 있으므로, 메모이제이션이 필수적입니다.

예제 1: 피보나치 수열 🔢

문제 설명: n번째 피보나치 수를 계산합니다.

피보나치 수열은 전형적인 동적 프로그래밍 문제로, 처음 두 항이 0과 1이고 그 다음 항부터는 앞의 두 항의 합으로 정의됩니다. 하향식 방법은 이 문제에 적합하며, 재귀 호출과 메모이제이션을 통해 효율성을 높일 수 있습니다.

import java.util.HashMap;

public class FibonacciBottomUp {
    private HashMap<Integer, Integer> cache = new HashMap<>();

    public int fib(int n) {
        if (n <= 1) return n;
        return cache.computeIfAbsent(n, key -> fib(key - 1) + fib(key - 2));
    }

    public static void main(String[] args) {
        FibonacciBottomUp fibSolver = new FibonacciBottomUp();
        System.out.println(fibSolver.fib(10)); // 출력 55
    }
}

이 구현에서는 HashMap을 사용하여 이미 계산된 값을 저장함으로써 중복 계산을 피합니다.

데이터 변화 표 📊

이 방법의 장점은 재귀 문제를 처리하는 데 매우 직관적이며 간결하다는 것입니다. 하지만 메모이제이션이 없다면 시간 복잡도가 O(n)에서 지수적으로 증가합니다.

예제 2: 배낭 문제 🎒

문제 설명: 물건들의 무게와 가치, 그리고 배낭의 용량이 주어졌을 때, 배낭에 넣을 수 있는 물건들의 조합 중 총 가치가 최대가 되는 경우를 찾습니다.

배낭 문제 역시 동적 프로그래밍에서 중요한 문제입니다. 하향식 방법에서는 물건의 개수와 배낭의 용량을 줄여가며 문제를 분해합니다. 각 부분 문제의 해를 메모이제이션으로 저장하면, 반복 계산을 줄여서 알고리즘의 효율성을 높일 수 있습니다.

import java.util.HashMap;

public class KnapsackTopDown {
    private HashMap<String, Integer> cache = new HashMap<>();

    public int knapsack(int[] weights, int[] values, int capacity, int n) {
        if (n == 0 || capacity == 0) return 0;
        String key = n + "," + capacity;
        return cache.computeIfAbsent(key, k -> {
            if (weights[n - 1] > capacity) {
                return knapsack(weights, values, capacity, n - 1);
            } else {
                int include = values[n - 1] + knapsack(weights, values, capacity - weights[n - 1], n - 1);
                int exclude = knapsack(weights, values, capacity, n - 1);
                return Math.max(include, exclude);
            }
        });
    }

    public static void main(String[] args) {
        KnapsackTopDown solver = new KnapsackTopDown();
        int[] weights = {1, 2, 3, 8};
        int[] values = {10, 15, 40, 50};
        int capacity = 5;
        System.out.println(solver.knapsack(weights, values, capacity, weights.length)); // 출력 55
    }
}

배낭 문제의 하향식 해결 방법에서는 각 물건이 배낭에 포함될지 여부와 해당 용량에서의 최적 해를 고려합니다.

데이터 변화 표 📊

이 방법은 복잡한 조합 문제를 처리할 수 있지만, 깊은 재귀 호출로 인한 성능 저하가 발생할 수 있습니다.

예제 3: 계단 오르기 문제 🏃‍♂️

문제 설명: n개의 계단을 올라가야 하는데, 한 번에 1계단 또는 2계단씩 올라갈 수 있습니다. 계단 꼭대기에 도달하는 서로 다른 방법의 수를 구하세요.

이 문제는 재귀를 사용하여 해결할 수 있으며, 메모이제이션을 통해 중간 결과를 저장합니다.

import java.util.HashMap;

public class ClimbStairsTopDown {
    private HashMap<Integer, Integer> cache = new HashMap<>();

    public int climbStairs(int n) {
        if (n <= 2) return n;
        return cache.computeIfAbsent(n, key -> climbStairs(key - 1) + climbStairs(key - 2));
    }

    public static void main(String[] args) {
        ClimbStairsTopDown solver = new ClimbStairsTopDown();
        System.out.println(solver.climbStairs(5)); // 출력 8
    }
}

데이터 변화 표 📊

이 방법은 재귀의 깊이를 줄이고, 이미 계산된 결과를 저장하여 중복 계산을 피함으로써 알고리즘의 효율성을 크게 향상시킵니다.

2. 상향식(📈 반복)

상향식 방법은 반복을 통해 가장 작은 문제부터 시작하여 원래 문제의 해를 구합니다. 이 방법은 재귀 호출 없이 문제를 해결하므로 스택 오버플로우 문제를 피할 수 있습니다. 배열을 사용하여 각 부분 문제의 해를 저장하고, 이를 통해 최종 답을 구합니다.

예제 1: 피보나치 수열 🔢

문제 설명: n번째 피보나치 수를 계산합니다.

상향식 방법을 사용하여 피보나치 수열의 n번째 항을 계산하면, 가장 작은 문제부터 시작하여 점차 큰 문제로 확장해 나갑니다.

public class FibonacciBottomUp {
    public int fib(int n) {
        if (n <= 1) return n;
        int prev1 = 0, prev2 = 1;
        for (int i = 2; i <= n; i++) {
            int current = prev1 + prev2;
            prev1 = prev2;
            prev2 = current;
        }
        return prev2;
    }

    public static void main(String[] args) {
        FibonacciBottomUp fibSolver = new FibonacciBottomUp();
        System.out.println(fibSolver.fib(10)); // 출력 55
    }
}

데이터 변화 표 📊

이 방법은 공간 복잡도가 낮아 실용적입니다.

3. 메모이제이션(💾)

메모이제이션 방법은 재귀를 사용하지만, 중간 결과를 저장하여 중복 계산을 피합니다. 이 방법은 재귀의 직관성과 캐싱 기술의 효율성을 결합하여 많은 복잡한 문제를 효과적으로 해결할 수 있습니다.

예제: 최소 경로 합 🛤️

문제 설명: m x n 크기의 그리드가 주어질 때, 각 칸에는 음이 아닌 정수가 있습니다. 왼쪽 위 모서리에서 오른쪽 아래 모서리까지 가는 최소 경로 합을 구하세요.

import java.util.Arrays;

public class MinPathSumMemo {
    private int[][] memo;

    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        memo = new int[m][n];
        for (int[] row : memo) Arrays.fill(row, -1);
        return dfs(grid, m - 1, n - 1);
    }

    private int dfs(int[][] grid, int i, int j) {
        if (i < 0 || j < 0) return Integer.MAX_VALUE;
        if (i == 0 && j == 0) return grid[0][0];
        if (memo[i][j] != -1) return memo[i][j];
        int left = dfs(grid, i, j - 1);
        int up = dfs(grid, i - 1, j);
        memo[i][j] = grid[i][j] + Math.min(left, up);
        return memo[i][j];
    }

    public static void main(String[] args) {
        MinPathSumMemo solver = new MinPathSumMemo();
        int[][] grid = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
        System.out.println(solver.minPathSum(grid)); // 출력 7
    }
}

데이터 변화 표 📊

이 방법은 재귀와 캐싱을 결합하여 복잡한 문제를 해결하는 데 매우 효과적입니다.