DP

동적 계획법(dynamic programming)은 복잡한 문제를 여러개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법을 뜻합니다.

동적 계획법의 핵심 이론

동적 계획법의 원리와 구현 방식은 다음과 같습니다.

동적 계획법의 원리와 구현 방식

큰 문제를 작은 문제로 나눌 수 있어야 한다.
작은 문제들이 반복되어 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 한다.
모든 작은 문제들은 한 번만 계산해 DP테이블에 저장하며 추후 재사용할 때는 이 DP테이블을 이용한다. 이를 메모이제이션(memoization)기법이라고 한다.
동적 계획법은 톱-다운 방식(top-down)과 바텀-업 방식(bottom-up) 방식으로 구현할 수 있다.

동적 계획법의 예

피보나치 수열을 예로 들어 설명한다.

D[N] = D[N-1] + D[N-2]

동적 계획법으로 풀 수 있는지 확인하기
6번째 피보나치 수열은 5번째 피보나치 수열과 4번째 피보나치 수열의 합이다. 즉 6번째 피보나치 수열을 구하는 문제는 5번째 피보나치 수열과 5번째 피보나치 수열을 구하는 작은 문제로 나눌 수 있고, 수열의 값은 항상 같기 때문에 동적 계획법으로 풀 수 있다.
점화식 세우기
점화식을 세울 때는 논리적으로 전체 문제를 나누고, 전체 문제와 부분 문제 간의 인과 관계를 파악하는 훈련이 필요합니다. 이 부분은 다양한 실전 문제를 풀면서 자연스럽게 훈련됩니다.
메모이제이션 원리 이해하기
메모이제이션은 부분 문제를 풀었을 때 이 문제를 DP테이블에 저장해 놓고 다음에 같은 문제가 나왔을 때 재계산하지 않고 DP테이블의 값을 이용하는 것을 말합니다. 다음 그림을 보면 위에서 2번째와 3번째 피보나치 수열은 맨 왼쪽 탐색 부분에서 최초로 값이 구해지고, 이때 DP테이블에 값이 저장됩니다. 이에 따라 나중에 2번째와 3번째 피보나치 수열의 값이 필요할 때 재연산을 이용해 구하지 않고, DP테이블에서 바로 값을 추출합니다. 이러한 방식을 사용하면 불필요한 연산과 탐색이 줄어들어 시간 복잡도 측면에서 많은 이점을 가질 수 있습니다.
톱-다운 구현 방식 이해하기
톱-다운 구현 방식은 말 그대로 위에서부터 문제를 파악해 내려오는 방식으로, 주로 재귀(recursion)함수 형태로 코드를 구현합니다. 코드의 가독성이 좋고, 이해하기가 편하다는 장점이 있습니다.

public class TopDown{
    static int[] dp;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        dp = new int[T+1];
        for (int i=0; i<=T; i++){
            dp[i] = -1;
        }
        dp[0] = 0;
        dp[1] = 1;
        fibonacci(T);
        System.out.println(dp[T]);
    }
    static int fibonacci(int N){
        // 기존에 계산한 적이 있는 부분의 문제는 재계산하지 않고 리턴한다.
        if (dp[N] != -1) return dp[N];
        //메모이제이션 : 구한 값을 바로 리턴하지 않고 DP테이블에 저장한 후 리턴하도록 로직을 구현한다.
        return dp[n] = fibonacci(n-2) + fibonacci(n-1);
    }
}

바텀-업 구현 방식 이해하기
가장 작은 부분 문제부터 문제를 해결하면서 점점 큰 문제로 확장해 나가는 방식입니다. 주로 반복문의 형태로 구현합니다.

public class BottomUp{
 static int[] dp;
 public static void main(String[] args){
     Scanner sc = new Scanner(System.in);
     int T = sc.nextInt();
     dp = new int[T+1];
     for (int i=0; i<=T; i++){
         dp[i] = -1;
     }
     dp[0] = 0;
     dp[1] = 1;
     for (int i=2; i<= T; i++){
         dp[i] = dp[i-1] + dp[i-2];
     }
     System.out.println(dp[T]);
 }
}

두 방식 중 좀 더 안전한 방식은 바텀-업입니다. 톱-다운 방식은 재귀 함수의 형태로 구현돼어 있기 때문에 재귀의 깊이가 매우 깊어질 경우 런타임 에러가 발생할 수 있습니다. 하지만 실제 코테에서 이 부분까지 고려해야 하는 난이도는 잘 나오지 않습니다. 자신에게 좀 더 편한 방식이나 문제에 따라 두 방식 중 1개를 선택해 사용하면 됩니다.