동적 계획법(DP:Dynamic programming) 개념 및 구현

동적 계획법은 복잡한 문제를 작은 하위 문제로 나누어 해결하고, 그 결과를 저장하여 동일한 하위 문제가 다시 나타날 때 재활용함으로써 연산을 줄이는 알고리즘 설계 기법이다. DP는 다음과 같은 두 가지 중요한 특징이 있다. 

 

1. 최적 부분 구조 : 문제의 최적 해결 방법이 하위 문제들의 최적 해결 방법으로 구성될 수 있다. 

2. 중복되는 부분 문제 : 동일한 작은 문제들이 반복적으로 계산된다. 

 

또한 DP에는 메모이제이션(탑다운), 타뷸레이션(바텀업) 2가지 방법이 있다.

비효율적인 재귀를 이용한 비보나치 수열 구현

public class FibonacciRecursive {
    public static void main(String[] args) {
        int n = 10; // 예를 들어 10번째 피보나치 수를 계산
        System.out.println(fib(n));
    }

    public static int fib(int n) {
        if (n <= 1) {
            return n;
        }
        return fib(n - 1) + fib(n - 2);
    }
}

구현 : 

1. 메모이제이션

public class FibonacciMemoization {
    public static void main(String[] args) {
        int n = 10; // 예를 들어 10번째 피보나치 수를 계산
        int[] memo = new int[n + 1];
        System.out.println(fib(n, memo));
    }

    public static int fib(int n, int[] memo) {
        if (n <= 1) {
            return n;
        }
        if (memo[n] != 0) {
            return memo[n];
        }
        memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
        return memo[n];
    }
}

 

2. 타뷸레이션(탑다운 방식)

public class FibonacciTopDown {
    public static void main(String[] args) {
        int n = 10; // 예를 들어 10번째 피보나치 수를 계산
        System.out.println(fib(n));
    }

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