[알고리즘] 동적 프로그래밍, 다이나믹 프로그래밍, DP :: seoftware

정의

동적 프로그래밍은 큰 문제의 해답에 작은 문제의 해답이 포함(최적부분구조)되어 있고, 이를 재귀호출 알고리즘으로 구현하면 지나친 중복이 발생하는 경우에 이 재귀적 중복을 해결하는 방법을 뜻한다.

정의로 유추할 수 있는 것 -> 최적부분구조가 발견되고, 재귀를 사용했을 때 중복 호출이 많을 때는 DP를 사용한다!

---

예시 - 피보나치

< 재귀호출을 사용한 경우 >

int fibo(int n) {
    if(n == 0) return 0;
    else if(n == 1) return 1;
    else return fibo(n-1) + fibo(n-2);
}

코드는 간단해보이지만 중복 호출이 많기 때문에 비효율적이다.

fibo(7)을 호출하면 fibo(2)가 몇번이나 호출되는지 확인해보자

fibo(7) 호출

fibo(7)을 구하기 위해 fibo(2)가 8번 호출 되는 것을 볼 수 있다. n의 값이 7이 아니라 더 커진다면 중복 호출은 훨씬 많아지고 해를 구하기 위한 시간이 오래걸릴 것이다. 

따라서 이런 경우에는 재귀 호출 보다는 동적 프로그래밍을 사용하는 것이 바람직하다.

 < DP를 사용한 경우 > 

int arr[100];
void fibo(int n) {
    arr[0] = 0; arr[1] = 1;
    for(int i = 2; i<=n; i++) {
        arr[i] = arr[i-1]+arr[i-2];
    }
}

dp를 사용하는 방법에는 top-down 방식과 bottom-up 방식이 있는데 위는 bottom-up 방식이다. 중복 호출이 발생하지 않는다! 

---

DP를 사용하려고 할 때 팁은 

1. 주로 배열에 값을 저장한다. 

2. 관계식이 존재한다. 어떤 관계가 있는지 파악하는 것이 중요!

3. 구하려는 값(n)부터 해결할 생각만 하지말고 0부터 시작해서 n까지 만들어갈 생각의 전환이 필요하다!