다이나믹 프로그래밍(동적 계획법)

---

복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 알고리즘이다.

조건 및 필수 개념

---

1. 큰 문제를 작은 문제로 나눌 수 있어야 한다.
2. 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결과값은 항상 같아야 한다.

💡메모이제이션 기법이란?
부분 문제를 풀었을 때, 이 문제를 DP 테이블에 저장해 놓고 다음에 같은 문제가 나왔을 때 재계산하지 않고 DP 테이블의 값을 이용하는 것을 말한다.

2가지 방식

---

다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시인 피보나치 수열로 다이나믹 프로그래밍의 2가지 방식(탑다운과 보텀업)을 설명한다.

탑다운(Top-Down) 방식 - 하향식

재귀 함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법으로, 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식이다.

• 코드의 가독성이 좋고, 이해하기 편하다는 장점이 있다.

public static long fibo(int x) {
        System.out.print("f(" + x + ") ");
        if (x == 1 || x == 2) {
            return 1;
        }
        // 기존에 계산한 적이 있는 부분의 문제는 재계산하지 않고 리턴
        if (d[x] != 0) {
            return d[x];
        }
        // 메모이제이션: 구한 값을 바로 리턴하지 않고 DP 테이블에 저장한 후 리턴하도록 로직을 구현
        d[x] = fibo(x - 1) + fibo(x - 2);
        return d[x];
    }

보텀업(Bottom-Up) 방식 - 상향식

단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출하는 방식이다.

• 탑다운보다 더 안정한 방식이다. 왜냐하면, 탑다운 방식은 재귀 함수의 형태로 구현돼 있기 때문에 재귀의 깊이가 깊어질 경우 런타임 에러가 발생할 수 있다. (하지만 실제 코딩 테스트에서 이 부분까지 고려해야 하는 난이도는 잘 나오지 않습니다!)

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]);
    }