[알고리즘] 동적계획법 DP Java 예제

동적계획법 DP(Dynamic Programming)이란 프로그램의 실행에 필요한 메모리를 할당하는 기법을 의미합니다.
동적계획법 DP 의 예제 중 가장 유명한 피보나치수열을 예로 들어보겠습니다.

1. 재귀 코드

public class Fibonacci {
    public static void main(String[] args) {
        int n = 10; // 피보나치 수열의 항 번호
        for (int i = 1; i <= n; i++) {
            System.out.print(fibonacci(i) + " ");
        }
    }

    // 피보나치 수열을 재귀적으로 계산하는 메소드
    public static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }
}

• 위와 같이 재귀 함수를 이용하면 같은 함수를 중복 호출하기 때문에 시간복잡도 O(2^n)을 갖게 됩니다. 

 

2. DP 코드

public class FibonacciDP {
    public static void main(String[] args) {
        int n = 10; // 피보나치 수열의 항 번호
        for (int i = 1; i <= n; i++) {
            System.out.print(fibonacci(i) + " ");
        }
    }

    // 동적 계획법을 사용하여 피보나치 수열을 계산하는 메소드
    public static int fibonacci(int n) {
        int[] fib = new int[n + 1];
        fib[0] = 0;
        fib[1] = 1;
        for (int i = 2; i <= n; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }
        return fib[n];
    }
}

• 위와 같이 DP를 이용하면 중복 호출이 해결되어 시간복잡도는 O(n)이 되고 입력크기에 비례하여 선형적으로 증가합니다.

 

3. 두 방식의 차이

1. 재귀적 방법: 이전 항의 값을 사용하여 다음 항을 계산합니다. 재귀 호출을 사용하므로 중복 계산이 발생하므로 시간 복잡도가 높을 수 있습니다.
   
   
2. 동적 계획법: 중복 계산을 피하기 위해 이전에 계산한 값을 배열에 저장하고 필요할 때마다 해당 값을 참조합니다. 이를 통해 효율적으로 계산하여 시간 복잡도가 더 낮습니다.

동적 계획법을 사용하는 경우 메모리를 추가로 사용하여 결과를 저장해야 하지만, 계산 시간을 절약할 수 있습니다. 따라서 피보나치수열과 같이 중복 계산이 많은 문제에는 동적 계획법이 더 효율적입니다.


감사합니다.