동적 계획법

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

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

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

피보나치 수열로 보는 동적 계획법

*동적 계획법의 가장 대표적이고 기본적인 문제가 피보나치 수열

피보나치 수열 공식
D[N] = D[N - 1] + D[N - 2]

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

6번째 피보나치 수열은 5번째 피보나치 수열 + 4번쨰 피보나치 수열이다. 즉 6번째 피보나치 수열을 구하는 문제는 5번째 피보나치 수열과 4번째 피보나치 수열을 구하는 작은 문제로 나눌 수 있고, 수열의 값은 항상 같기 때문에 동적 계획법으로 풀 수 있다.

2. 점화식 세우기

점화식을 세울 때는 논리적으로 전체 문제를 작은 문제로 분할하고, 전체 문제와 부분 문제 간의 인과관계를 파악하여야한다.(이 부분은 여러 문제를 풀이하면서 체득 해야한다.)
피보나치 수열 예제는 공식 자체가 점화식이므로 공식을 점화식으로 사용

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

메모이제이션은 부분 문제를 풀었을 때 이 문제를 DP 테이블(배열 등)에 저장해 놓고 다음에 같은 문제가 나왔을 때 재계산하지 않고 DP 테이블의 값을 이용하는 것.
이 방식을 사용하면 불 필요한 연산과 탐색이 줄어들어 시간 복잡도 측면에서 많은 이점을 가질 수 있다.

4-1. 탑다운 구현 방식

탑다운 구현은 말 그대로 제일 상위에서부터 문제를 파악해 내려오는 방식으로, 주로 재귀 함수 형태로 코드를 구현한다. 코드의 가독성이 좋고, 이해하기가 편하다는 장점이 있다.

public class Main {
    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);
        System.out.println(D[n]);
    }

    static int fibo(int n) {
        if (D[n] != =1) { // 기존에 계산한 문제라면 재계산 x
            return D[n];
        }
        return D[n] = fibo(n - 2) + fibo(n - 1);
        // 값을 바로 리턴하지 않고 DP 테이블에 저장한 후 리턴하도록 로직 구현
    }
}

4-2. 바텀업 구현 방식

가장 작은 부분 문제부터 문제를 해결하면서 점점 큰 문제로 확장해 나가는 방식으로 주로 반복문의 형태로 구현한다.

public class Main {
    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]);
    }
}