DP(Dynamic Programming) 알고리즘

Dynamic Programming

DP는 큰 문제를 작은 문제로 분할하여 그것을 이용해 큰 문제를 해결하는 방법이다. 분할정복(퀵 정렬)과 다른점은 DP의 경우 작은 부분 문제의 답이 항상 같아야 한다는 것이다.

사전 조건

1. 작은 문제들이 반복된다.
2. 같은 문제는 구할 때마다 정답이 같아야 한다.

모든 작은 문제들은 한번만 풀어야한다. 정답을 구한 작은 문제를 어딘가에 메모해 놓는다. 다시 그보다 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제의 결과값을 이용한다.

DP 종류

1. Bottom-up : 작은 문제부터
2. Top-down : 재귀함수로 구현하는 경우. 메모이제이션 사용

• 메모이제이션 : 반복되는 결과를 메모리에 저장(DP table), 한 번 더 계산하지 않고 재활용, 캐싱이라고도 한다.

피보나치수열 DP알고리즘으로 풀기

Top-down

public class Main {

    // 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 배열 초기화
    public static long[] d = new long[100];

    // 피보나치 함수(Fibonacci Function)를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
    public static long fibo(int x) {
        // 종료 조건(1 혹은 2일 때 1을 반환)
        if (x == 1 || x == 2) {
            return 1;
        }
        // 이미 계산한 적 있는 문제라면 그대로 반환
        if (d[x] != 0) {
            return d[x];
        }
        // 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
        d[x] = fibo(x - 1) + fibo(x - 2);
        return d[x];
    }

    public static void main(String[] args) {
        System.out.println(fibo(50));
    }
}

Bottom-up

public class Main {

    public static long[] d = new long[100];

    public static void main(String[] args) {
        // 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
        d[1] = 1;
        d[2] = 1;
        int n = 50; // 50번째 피보나치 수를 계산

        // 피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍)
        for (int i = 3; i <= n; i++) {
            d[i] = d[i - 1] + d[i - 2];
        }
        System.out.println(d[n]);
    }
}

추가 참고하면 좋을 블로그
https://sskl660.tistory.com/87?category=845237