동적 계획법, 동적 프로그래밍

재귀와 같이,, 자기 자신을 계속 호출하는 형태의 함수에서

각 함수의 결과를 미리 저장해 놓고, 호출시 저장된 값을 활용해 시간을 단축하는 방법

가령 피보나치 수열을 예로

위 그림과 같이 계속 반복되는 부분이 있을 때,,

초기 매개변수가 작다면 실행 시간에 큰 차이가 없지만,,

매개변수가 커졌을 때, 매번 그 부분을 계산하는 것은 매우 비효율적이다.

따라서 그 값을 저장해둔다.

아래는 비교

- 동적 계획법 X

/**
 * 일반 재귀
 * @param n
 * @return
 */
public static int fibo(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;
    } else {
        return fibo(n - 2) + fibo(n -1);
    }
}

- 동적 계획법 O

static int[] dp;

/**
 * 동적 계획법 사용
 * @param n
 * @return
 */
public static int fiboDynamic(int n) {
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        return 1;

        /**
         * 이전에 계산을 했다면 저장된 값 리턴
         */
    } else if (dp[n] != -1) {
        return dp[n];
    } else {
        dp[n] = fiboDynamic(n - 2) + fiboDynamic(n - 1);
        return dp[n];
    }
}

시간 비교..

public static void main(String args[]) {
    int n = 48;

    long s1 = System.currentTimeMillis();
    System.out.println(fibo(n));
    long e1 = System.currentTimeMillis();
    System.out.println("일반 : " + (e1 - s1));

    System.out.println("-----------");

    dp = new int[n + 1];
    for (int i = 0; i < dp.length; i++) {
        dp[i] = -1;
    }

    long s2 = System.currentTimeMillis();
    System.out.println(fiboDynamic(n));
    long e2 = System.currentTimeMillis();
    System.out.println("동적 : " + (e2 - s2));
}

512559680

일반 : 23160

-----------

512559680

동적 : 1