[Algorithm 기초] 다이나믹 프로그래밍

다이나믹 프로그래밍 (Dynamic Programming, DP)

- 큰 문제를 부분 문제로 나눈 후 답을 찾아가는 과정에서, 계산된 결과를 기록하고 재활용하며 문제의 답을 구하는 방식

- 중간 계산 결과를 기록하기 위한 메모리가 필요

- 한 번 계산한 부분을 다시 계산하지 않아 속도 빠름

 

분할 정복과의 차이

- 분할 정복은 부분 문제가 중복되지 않음

- DP는 부분 문제가 중복되어 재활용에 사용

 

그리디 알고리즘과의 차이

- 그리디 알고리즘은 순간의 최선을 구하는 방식(근사치)

- DP는 모든 방법을 확인 후 최적해 구하는 방식

 

사용 예제01

// 피보나치 수열 (일반 풀이 - O(n^2))
// 계산했던 부분도 다시 계산
public static int fib(int n) {
    if (n <= 1) {
        return n;
    } else {
        return fib(n - 1) + fib(n - 2);
    }
}

 

 

다이나믹 프로그래밍 방법

1. 타뷸레이션 Tabulation

- 상향식 접근 방법

- 작은 하위 문제부터 풀면서 올라가고, 모두 계산하면서 차례대로 진행

// 피보나치 수열 (DP 풀이 - 타뷸레이션 - O(n))
public static int fibDP(int n) {
    // DP 용 메모리 필요
    int[] dp = new int[n < 2 ? 2 : 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];
}

 

 

2. 메모리제이션 Memorization

- 하향식 접근 방법

- 큰 문제에서 하위 문제를 확인해가면서, 계산이 필요한 순간에 계산하며 진행

// 피보나치 수열 (DP 풀이 - 메모이제이션)
static int[] dp = new int[8];
public static int fibDP2(int n) {
    if (n <= 2) {
        return 1;
    }

    // 기록해둔 게 있으면 사용
    if (dp[n] != 0) {
        return dp[n];
    }

    // 없으면 하위 호출
    dp[n] = fibDP2(n - 1) + fibDP2(n - 2);
    return dp[n];
}