다이나믹 프로그래밍(DP)에 대해 알아보자.

다이나믹 프로그래밍이라는 이야기는 많이 들어보았지만 ... 아직도 잘 와닿지 않고 막상 문제를 풀려고 할 때마다 어려운 부분이 바로 DP일 것이다.

거창해 보이는 이름과는 달리 간단하게 생각하여 2가지 조건을 만족한다면 DP로 접근을 한다고 생각하면 쉬울것이다.

1) overlapping subproblem (겹치는 부분문제)

2) Optimal substructure (최적 부분 구조) 이다.

겹치는 부분문제의 경우에는 피보나치 수열을 생각하면 쉽다. 피보나치 수열을 구하기 위해서는 예 n번째 수를 구하기 위해서 n-1, n-2의 값을 구해야 하는것처럼 말이다.

다이나믹 프로그래밍에서는 각 문제를 한번만 풀어야한다. 같은 문제는 구할 때마다 정답이 같기때문이다. 따라서 정답을 한번 구했으면 어딘가에 메모해놓게된다.

이러한 메모를 코드의 구현에서는 배열에 저장하는 방식을 사용한다. 이를 바로 메모이제이션이라고 한다.

int memo[100];

int fibonacci(int n) {

    if (n <= 1) {

        return n;

    } else {

        if (memo[n] > 0) {

            return memo[n];

        }

        memo[n] = fibonacci(n-1) + fibonacci(n-2);

        return memo[n];

    }

}

이러한 코드가 예사기 될 수 있을 것이다.

이러한 다이나믹을 푸는 방법에는 두 가지로 나누어 볼 수 있다.

1) Top-down

2) Bottom-Up

Top-down의 경우에는 문제를 작은 문제로 나누고 작은 문제를 푼 후 실제 문제를 푸는 방식이고,

Bottom-up의 경우에는 문제를 작은 음 .... 

                             

왼쪽이 Tio-down 방식이고 오른쪽이 Bottom-up방식이다.

DP는... 이렇게 말을 하는것보다 실제로 문제를 풀면서 체득하는것이 더빠를것이다. 그럼 ... 빨리 문제 풀러 가자 ㅋㅋㅋ