[알고리즘] 동적계획법(Dynamic Programming : DP)

동적 계획법(Dynamic Programming)이란?

동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 작은 하위 문제들로 나누어 그 결과를 저장하고, 이를 바탕으로 전체 문제를 해결하는 알고리즘 기법입니다. 하위 문제들이 반복될 때, 이를 재계산하지 않고 저장해둔 결과를 재사용함으로써 효율적으로 문제를 해결합니다.

동적 계획법의 특징

1. 중복되는 하위 문제: DP는 하위 문제들이 반복적으로 나타날 때 유용합니다. 예를 들어, 피보나치 수열을 계산할 때, 여러 번 동일한 계산을 해야 하는 경우가 많습니다. 이 때, 계산 결과를 저장해 중복 계산을 피할 수 있습니다.
2. 최적 부분 구조: 문제의 최적 해결 방법이 그 하위 문제들의 최적 해결 방법으로부터 결정되는 구조입니다. 즉, 큰 문제를 작은 문제로 나눠서 풀고, 작은 문제의 해를 결합하여 큰 문제의 해를 구할 수 있는 경우에 DP를 사용할 수 있습니다.
3. 메모이제이션(Memoization) 또는 테이블화(Tabulation):
   • 메모이제이션: 재귀적 접근법에서 이미 계산한 결과를 저장해 두고, 동일한 계산을 다시 할 때 그 결과를 반환하는 방식입니다.
   • 테이블화: 문제의 크기에 따라 결과를 테이블(배열)에 저장하고, 작은 크기에서 큰 크기로 순차적으로 해결하는 방식입니다.
4. 상향식(Bottom-up) 접근: DP는 일반적으로 작은 하위 문제부터 시작하여 점차 큰 문제를 해결하는 방식으로 구현됩니다. 이는 주로 반복문을 사용하여 테이블에 값을 채워나가는 형태로 구현됩니다.

동적 계획법의 예시

피보나치 수열

피보나치 수열은 DP의 대표적인 예시입니다. 피보나치 수열은 다음과 같이 정의됩니다:

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) (n ≥ 2)

이 수열을 계산할 때, DP를 사용하면 중복되는 계산을 피할 수 있습니다.

탑다운(메모이제이션) 방식:

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

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

    public 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) {
        FibonacciMemoization fib = new FibonacciMemoization();
        System.out.println("Fibonacci of 10: " + fib.fib(10));  // Output: 55
    }
}

바텀업(테이블화)방식:

public class FibonacciTabulation {
    public int fib(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) {
        FibonacciTabulation fib = new FibonacciTabulation();
        System.out.println("Fibonacci of 10: " + fib.fib(10));  // Output: 55
    }
}

 

 

동적 계획법의 활용 분야

동적 계획법은 다양한 분야에서 사용됩니다:

• 문자열 매칭: 예를 들어, 편집 거리(Edit Distance) 계산.
• 조합 최적화: 배낭 문제, 여행하는 세일즈맨 문제 등.
• 게임 이론: 최적의 게임 전략 찾기.
• 수열 문제: 가장 긴 증가하는 부분 수열(LIS) 등.