동적 계획법 (Dynamic Programming)

동적 계획법(DP)은 복잡한 문제를 간단한 여러 개의 작은 문제로 나누어 해결하는 알고리즘 기법입니다. 이는 똑같은 연산을 반복하지 않도록 만들어주는 알고리즘으로, 실행 시간을 줄이기 위해 많이 활용됩니다. DP는 특히 Optimal Substructure(최적 부분 구조)에서 효과적으로 사용됩니다.

Optimal Substructure

Optimal Substructure는 큰 문제를 작은 문제로 나눌 수 있는 문제 구조를 의미합니다. 이 구조를 갖는 문제는 동일한 계산이 반복되므로, 동적 계획법을 사용하면 효율적으로 해결할 수 있습니다.

접근 방식

동적 계획법은 큰 문제를 작은 문제로 나누어 해결하는 방식으로, 분할 정복(Divide and Conquer)과 매우 유사합니다. 그러나 동적 계획법은 "반복되는 연산"을 활용하여 문제를 효율적으로 해결하는 것이 핵심입니다.

조건

동적 계획법이 적용되기 위한 조건은 다음과 같습니다:
1. 작은 문제에서 반복이 일어남: 작은 문제들이 반복적으로 사용됩니다.
2. 같은 문제는 항상 정답이 같음: 동일한 문제에 대해 항상 같은 결과를 반환합니다.

이 두 가지 조건이 충족된다면, 동적 계획법을 통해 문제를 최적화하여 풀 수 있습니다. 이를 위해 메모이제이션(Memoization) 기법을 사용합니다.

메모이제이션 (Memoization)

메모이제이션은 한 번 계산한 결과를 저장해두고, 동일한 계산이 필요할 때 저장된 값을 재사용하는 방식입니다. 이를 통해 반복적인 계산을 줄이고, 연산 효율을 크게 높일 수 있습니다.

예를 들어, 피보나치 수열을 재귀적으로 계산할 때, 동일한 계산이 여러 번 반복됩니다. 메모이제이션을 활용하면 이러한 반복 계산을 방지할 수 있습니다.

import java.util.HashMap;
import java.util.Map;

public class FibonacciDP {
    private Map<Integer, Integer> memo = new HashMap<>();

    public 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) {
        FibonacciDP fib = new FibonacciDP();
        System.out.println("Fibonacci(10): " + fib.fibonacci(10));
    }
}

동작 설명

1. fibonacci(n) 함수는 n번째 피보나치 수를 반환합니다.
2. 계산된 결과는 memo라는 해시맵에 저장되어, 동일한 계산이 필요할 때 저장된 값을 재사용합니다.
   3.이로 인해 피보나치 수열을 계산할 때 시간 복잡도가 O(2^n)에서 O(N)으로 크게 줄어듭니다.

구현 방식

동적 계획법은 주로 두 가지 방식으로 구현됩니다:

Bottom-up

작은 문제부터 차근차근 해결해 나가는 방식입니다. 이는 DP 테이블을 채우면서 문제를 해결하며, 반복문을 통해 구현합니다.

Top-down

큰 문제를 먼저 해결하려고 시도하다가, 필요할 때 작은 문제를 해결하는 방식입니다. 주로 재귀를 통해 구현되며, 메모이제이션과 함께 사용됩니다.

Bottom-up 예제 (피보나치 수열)

public class FibonacciBottomUp {
    public 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) {
        FibonacciBottomUp fib = new FibonacciBottomUp();
        System.out.println("Fibonacci(10): " + fib.fibonacci(10));
    }
}

So...

동적 계획법은 반복적인 계산을 피하고, 효율적으로 문제를 해결할 수 있는 강력한 알고리즘 기법입니다. 문제를 작은 단위로 나누고, 메모이제이션을 통해 이미 계산된 결과를 재사용함으로써 시간 복잡도를 크게 줄일 수 있습니다. 문제를 해결할 때, 작은 문제부터 접근하여 점화식을 도출하고 동적 계획법을 적용하는 것이 중요합니다.