[알고리즘] 다이나믹 프로그래밍

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

 

• 동적 계획법
• 어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는 알고리즘
• 즉, 답을 찾아가는 과정에서 계산된 결과를 기록하고 재활용하며 문제의 답을 구하는 방식
• 중간 계산 결과를 기록하기 위한 메모리가 필요
• 한 번 계산한 부분을 다시 계산하지 않기 때문에 속도가 빠름
• 타뷸레이션(Tabulation) : 상향식 접근 방법
• 메모이제이션(Memoization) : 하향식 접근 방법

 

원래 재귀 호출로 구현한 피보나치 수열을 DP를 이용해 구현해보자

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

 

 

 

1. 타뷸레이션

// 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. 메모이제이션

// DP - 메모이제이션
// n이 7이라고 가정하고 메모리 생성
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];
}