다이나믹 프로그래밍 정의

복잡한 큰 문제를 재귀적인 방식(재귀적인 방식이지 재귀 함수로 구현해야 하는것은 아니다)으로 간단한 하위 문제로 나누어 최종 큰 문제까지 해결할 수 있는 알고리즘 설계 기법, 주로 모든 경우의 수를 일일이 다 구해서 풀 수 있지만, 그 모든 경우의 수를 모두 구하기에는 시간이 오래 걸려 최적화 하기 위해 사용한다.

일반적으로는 메모이제이션(각 하위 문제의 연산 결과를 담아놓는 것)이라는 개념으로 효율성을 높인다.

다이나믹 프로그래밍 주요 속성

• 중복된 하위 문제(Overlapping Subproblems): 문제를 해결하는 과정에서 동일한 하위 문제가 반복적으로 발생하여, 이를 한 번만 계산하고 그 결과를 저장해 두었다가 필요할 때 재사용할 수 있음
• 최적 부분 구조 (Optimal Substructure): 복잡한 큰 문제의 최적 해결 방법이 그 문제의 하위 문제들의 최적 해결 방법으로부터 구성될 수 있다는 성질입니다. 즉, 하위 문제의 최적 해결책을 결합하여 전체 문제의 최적 해결책을 얻을 수 있습니다.

메모이제이션을 사용해야만 다이나믹 프로그래밍인가?

• NO

현 문제에 필요한 전의 부분문제 즉, 그 즉시 필요한 해만 임시적으로 저장 (이것도 메모이제이션이라고 해야 하나?)

• 쨌든 전체 부분문제를 모두 저장할 필요는 없음, 하지만 중복된 하위 문제 그리고 최적 부분 구조를 가진다는것은 동일함

public class FibonacciBottomUp {
    public static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        int a = 0; // 첫 번째 항
        int b = 1; // 두 번째 항
        int c = 1;
        for (int i = 2; i <= n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }

    public static void main(String[] args) {
        int n = 10; // 계산하고 싶은 피보나치 수열의 항
        System.out.println("피보나치 수열의 " + n + "번째 항의 값은 " + fibonacci(n) + "입니다.");
    }
}

그러면.. 투포인터도 이 전의 두 항만 저장하는거니까 DP라고 볼 수 있겠네?

• No
• 예를 들어, 정렬된 배열에서 두 수의 합이 특정 값에 해당하는 쌍을 찾는 경우, 배열의 양 끝에 포인터를 위치시키고, 두 포인터가 가리키는 값의 합을 계산한 후, 그 합이 목표 값보다 크거나 작을 경우 포인터를 조정하여 원하는 값을 찾는다. 이는 각 단계에서 이전 두 항을 저장하는 것과 유사할 수 있지만, 이러한 처리는 DP의 중요한 특징인 “부분 문제의 최적해를 저장하고 재활용한다”는 점과는 결이 다르다. 투 포인터는 주로 검색 및 정렬 문제에 적합하며, 이전 결과를 재활용하여 문제를 해결하는 DP의 전략과는 본질적으로 다르다.

다이나믹 프로그래밍 접근 방식

• Top-down 접근법 (Memoization): 큰 문제에서 시작하여 필요할 때 작은 문제로 나누어 해결하며, 각 하위 문제의 결과를 저장하는 방식입니다.
• Bottom-up 접근법 (Tabulation): 가장 작은 하위 문제부터 시작하여 점차적으로 문제를 확장해 나가면서 문제의 해결책을 테이블에 저장하는 방식입니다.

top down은 재귀, bottom up은 반복문 이라고 볼 수 있는가?

• No
• 예를 들어, 순열이나 조합과 같은 수학적 문제에서 하위 문제의 결과를 이용해 상위 문제를 해결하는 재귀 함수를 구현할 때, 작은 인덱스부터 큰 인덱스로 값을 구축해 나가는 방식으로 Bottom-up 접근을 재귀적으로 구현할 수 있습니다. 그러나 이런 경우는 상대적으로 드물고, 대부분의 Bottom-up 접근은 반복문을 이용하여 효율성을 높이는 방식으로 구현된다.

다이나믹 프로그래밍 문제 파악 (DP로 풀리는 문제인가?)

• 모든 경우의 수를 구해서 풀 수 있다.
• 단, 모든 경우의 수 중 이미 했던 중복 연산을 또 하지 않는 구조로 만들 수 있는가?
• 중복 연산을 하지 않기 위해, 어떤 정보를 기록해놓아야 하는가?