[Java/알고리즘] 다이나믹 프로그래밍(Dynamic Programming -DP)

다이나믹 프로그래밍이란?

• 작은 문제들을 풀면서 그 결과를 저장해 나아가면서 전체 문제를 해결하는 알고리즘을 의미한다.
• 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. - 메모이제이션(Memoization)

사용 조건

1. 최적 부분 구조 (Optimal Substructure)
   • '큰 문제의 최적해'가 '작은 문제의 최적해'를 포함하는 성질이다.
   • 즉, 작은 문제의 최적해를 구한 후 그것을 이용하여 큰 문제의 최적해를 구할 수 있다.
     
     
2. 중복 부분 문제 (Overlapping Subproblems)
   • '동일한 작은 문제를 반복적으로 해결'해야 하는 성질이다.
   • 즉, 작은 문제를 해결할 때 반복적으로 같은 문제를 해결해야 한다.

구현 방법

1. 탑다운(Top-Down) 방식 - 재귀적으로 호출하여 문제를 해결하는 방식

   해당 예시는 탑다운 방식을 이용하여 피보나치 수열을 계산하는 방식이다.
   
   n이 1보다 작거나 같은 경우에는 n을 반환하고, 그 외의 경우에는 fib(n-1)과 fib(n-2)를 더한 값을 dp 배열에 저장한 후 반환합니다. -> 저장하는 과정이 메모이제이션이다.

public class TopDownDP {
// 메모이제이션(Memoization)하기 위한 리스트 초기화
    static int[] dp = new int[101];

    public static int fibo(int n) {
    // 종료 조건 (1이하 일때)
        if (n <= 1) {
            return n;
        }
        
        // 이미 계산한 적이 있는 문제라면 그대로 반환
        if (dp[n] != 0) { // 메모이제이션
            return dp[n];
        }
        // 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과를 저장 후 반환
        dp[n] = fibo(n - 1) + fib(n - 2);
        return dp[n];
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println("fibonacci(" + n + ") = " + fibo(n));
    }
}

탑다운(Top-Down) 방식 특징
Bottom-up 방식에 비해 가독성이 좋고 본래 점화식을 이해하기 쉽지만, 코드 작성이 어렵고 재귀 함수가 가진 단점을 어느 정도 공유한다.

2. 바텀업(Bottom-Up) 방식 - ‘작은 문제’부터 해결하여 ‘큰 문제’까지 해결하는 알고리즘 방식

해당 방식은 탑 다운 방식과 비교하여 재귀적으로 수행하지 않고 ‘반복문’을 통해서 문제를 해결해 나아가는 방식이다.

public int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    int[] memo = new int[n+1];
    
    // memo[0]과 memo[1]은 초기값으로 설정
    memo[0] = 0;
    memo[1] = 1;
    
    //피보나치 함수(Fibonacci Function) 반복문으로 구현
    for (int i = 2; i <= n; i++) {
        memo[i] = memo[i-1] + memo[i-2];
    }
    return memo[n];
}

바텀업(Bottom-up) 방식 특징
문제를 풀기는 쉽지만 소스의 가독성은 어렵다는 단점이 있다.