Dynamic Programming(DP)

동적 계획법 Dynamic Programming이란?

동적 계획법은 큰 문제를 작은 문제로 나눠서 최종 문제를 해결하는 알고리즘입니다.

작은 문제를 처리할 때 수행되는 답을 저장해 놓고 다음번에 필요할 때 그 값을 불러와서 처리합니다. 재활용 개념이라고 이해하면 쉽습니다. 분할 정복과 비슷한 개념이지만 분할 정복과 동적 계획법의 차이점은 분할 정복에서의 쪼개진 작은 문제들은 중복되지 않지만 동적 계획법에서 쪼개진 문제는 서로 연관성이 있다는 점이다.

동적 계획법의 조건

▷ 겹치는 부분문제 - 어떤 문제가 여러 개의 작은 문제로 쪼개질 수 있어야 한다.

▷ 최적 부분구조 - 어떤 문제의 최적의 해결책이 그 부분 문제의 최적의 해결책으로부터 해결할 수 있어야 한다.

---

동적 계획법의 구현 방식

• Top-down 방식 (재귀) : 분할 정복, 큰 문제를 작은 문제들로 풀어나가는 방법.
• Bottom-up 방식 (반복문) : 작은 문제들을 먼저 풀어 큰 문제를 해결하는 방법.

---

/*재귀*/
public int fibonacci(int n){
    if(n<=1) return n;
    return fibonacci(n-1) + fibonacci(n-2);
}

-> 대부분 재귀로 푸는데 함수가 호출될 때마다 동일한 값을 반복해서 구해야 한다는 문제점이 있습니다.

예를 들어, fibonacci(4)를 구할 때 fib(2)가 중복되어 계산됩니다.

fib(4)
= fib(3) + fib(2)
= (fib(2) + fib(1)) + (fib(1) + fib(0))
= (fib(1) + fib(0)) + fib(1) + (fib(1) + fib(0))

해결책

메모이제이션(Memoization) : 함숫값을 계산한 뒤 계산된 값을 메모리에 저장하는 방식, 함수를 호출하지 않고 값을 빠르게 가져올 수 있습니다.

-> 한번 구해놓은 값을 다시 구하지 않아 불필요한 연산을 줄여 속도가 향상됩니다.

public int fibonacci(int n) {
    d[0] = 0;
    d[1] = 1;
    for (int i = 2; i <= n; i++) {
        d[i] = d[i - 1] + d[i - 2];
    }
    return d[n];
}