동적계획법(Dynamic Programming)

동적 계획법이란?

복잡한 문제를 여러 개의 간단한 문제로 분리해 부분의 문제를 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법

 

 

핵심 이론

1. 큰 문제를 작은 문제로 나눌 수 있어야 함

2. 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 함

3. 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용한다. = 메모이제이션

4. 동적 계획법은 톱-다운 & 바텀-업 방식으로 구현할 수 있음

 

 

대표적인 예 : 피보나치 수열

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

 

 

1. 동적 계획법으로 풀 수 있는지 확인

- 6번째 피보나치 수열은 5번째 피보나치 수열과 4번째 피보나치 수열의 합

- 6번째 피보나치 수열을 구하는 문제는 각 4, 5번째 피보나치 수열을 구하는 작은 문제를 나눌 수 있음

- 수열의 값은 항상 같기에 동적 계획법으로 풀 수 있음

 

 

2. 점화식 세우기

- 논리적으로 전체 문제를 나누고, 전체 문제와 부분 문제 간의 인과 관계를 파악하는 훈련 필요

- 피보나치 수열의 점화식은 D[N] = D[N-1] + D[N-2] 이 됨

 

 

3. 메모이제이션 원리 이해하기

- 부분 문제를 풀었을 때 이 문제를 DP 테이블에 저장해 놓고 다음에 같은 문제가 나왔을 때 재계산하지 않고 DP 테이블 값을 이용하는 것

- 불필요한 연산과 탐색이 줄어들어 시간 복잡도에서 이점이 있음

 

 

4. 톱 - 다운 구현 방식 이해하기

- 말 그대로 위에서부터 문제를 파악해 내려오는 방식으로 주로 재귀 함수로 구현

- 코드 가독성이 좋고 이해가 편함

public class TopDown {

    static int[] D;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        D = new int[n+1];

        for(int i=0; i<=n; i++) {
            D[i] = -1;
        }

        // 가장 작은 문제부터
        D[0] = 0;
        D[1] = 1;
        
        fibo(n);
    }
    
    static int fibo(int n) {
        
        // 기존에 계산한 적이 있는 문제는 바로 리턴 -> 재계산 X
        if(D[n] != -1) {
            return D[n];
        }
        
        // 바로 리턴하지 않고 DP x테이블에 저장한 루 리턴 = 메모이제이션!
        return D[n] = fibo(n-1) + fibo(n-2);
    }
}

 

 

5. 바텀 - 업 구현 방식 이해하기

- 가장 작은 부분 문제부터 해결하며 점점 큰 문제로 확장해 나가는 방식

- 주로 반복문 형태로 구현

public class BotomUp {

    static int[] D;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        D = new int[n+1];

        for(int i=0; i<=n; i++) {
            D[i] = -1;
        }

        // 가장 작은 문제부터
        D[0] = 0;
        D[1] = 1;
        
        // 바텀 업 방식
        for(int i=2; i<=n; i++) {
            D[i] = D[i-1] + D[i-2];
        }

        System.out.println(D[n]);
    }
}

 

=> 좀 더 편한 방식이나 문제에 따라 두 방식 중 1개를 선택해 사용하면 됨