동적 계획법(=다이나믹 프로그래밍(DP, Dynamic Programming))

• 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장해
  다시 큰 문제를 해결할 때 사용하는 것

  큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용

재귀와 다른 점

• 일반적인 재귀를 단순 사용 시 동일한 작은 문제들이 여러번 반복되어 비효율적인 계산이 됨
• DP를 사용하면 앞에서 계산된 값을 다시 반복할 필요가 없이 효율적으로 계산이 가능해짐

사용 조건

• 특정 데이터 내 최대화 / 최소화 계산 문제

• 특정 조건 내 데이터 개수 세기 문제

• 확률 계산 문제

• 다음 2가지 조건을 만족해야 함

  1. 동일한 작은 문제들이 반복하여 나타나는 경우 (부분 문제가 중복)

     💡 피보나치 수열 f(n) = f(n-1) + f(n-2)의 경우 예시
     

  2. 부분 문제의 최적 결괏값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우
     👉 특정 문제의 정답은 문제의 크기에 상관없이 항상 동일

DP 문제푸는 방법

1. 테이블 정의
   • 문제 내 변수 정하기
   • 피보나치 수열 문제: n번째 숫자를 구하는 것이므로 n이 변수
   • 문자열 간의 차이 문제: 문자열의 길이, edit 거리 등
   • Knapsack 문제: index, 무게
2. 점화식 찾기
3. 변수의 값에 따른 결과 저장하기
   • 변수 값에 따른 결과 저장할 배열 만들어 결과 저장
4. 초기값 정하기
   • 가장 작은 문제의 상태 파악

구현 방식

• Bottom-Up (Tabulation 방식) - 반복문 사용
• Top-Down (Memoization 방식) - 재귀 사용

Bottom-Up 방식

• 아래에서부터 계산을 수행하고 누적시켜서 큰 문제를 해결

Top-Down 방식

• 위에서부터 바로 호출을 시작
• dp[0]의 상태까지 내려간 다음, 해당 결괏값을 재귀를 통해 전이시켜 재활용

코드

public class Fibonacci{
    // DP 를 사용 시 작은 문제의 결과값을 저장하는 배열
    // Top-down, Bottom-up 별개로 생성하였음(큰 의미는 없음)
    static int[] topDown_memo; 
    static int[] bottomup_table;
    public static void main(String[] args){
        int n = 30;
        topDown_memo = new int[n+1];
        bottomup_table = new int[n+1];
        
        long startTime = System.currentTimeMillis();
        System.out.println(naiveRecursion(n));
        long endTime = System.currentTimeMillis();
        System.out.println("일반 재귀 소요 시간 : " + (endTime - startTime));
        
        System.out.println();
        
        startTime = System.currentTimeMillis();
        System.out.println(topDown(n));
        endTime = System.currentTimeMillis();
        System.out.println("Top-Down DP 소요 시간 : " + (endTime - startTime));
        
        System.out.println();
        
        startTime = System.currentTimeMillis();
        System.out.println(bottomUp(n));
        endTime = System.currentTimeMillis();
        System.out.println("Bottom-Up DP 소요 시간 : " + (endTime - startTime));
    }
    
    // 단순 재귀를 통해 Fibonacci를 구하는 경우
    // 동일한 계산을 반복하여 비효율적으로 처리가 수행됨
    public static int naiveRecursion(int n){
        if(n <= 1){
            return n;
        }
        return naiveRecursion(n-1) + naiveRecursion(n-2);
    }
    
    // DP Top-Down을 사용해 Fibonacci를 구하는 경우
    public static int topDown(int n){
        // 기저 상태 도달 시, 0, 1로 초기화
        if(n < 2) return topDown_memo[n] = n;
        
        // 메모에 계산된 값이 있으면 바로 반환!
        if(topDown_memo[n] > 0) return topDown_memo[n];
        
        // 재귀를 사용하고 있음!
        topDown_memo[n] = topDown(n-1) + topDown(n-2);
        
        return topDown_memo[n];
    }
    
    // DP Bottom-Up을 사용해 Fibonacci를 구하는 경우
    public static int bottomUp(int n){
        // 기저 상태의 경우 사전에 미리 저장
        bottomup_table[0] = 0; bottomup_table[1] = 1;
        
        // 반복문을 사용하고 있음!
        for(int i=2; i<=n; i++){
            // Table을 채워나감!
            bottomup_table[i] = bottomup_table[i-1] + bottomup_table[i-2];
        }
        return bottomup_table[n];
    }
}