챕터3-1. DP | 기초

다이나믹 프로그래밍의 개념

# 다이나믹 프로그래밍(DP, Dynamic Programming)
- 큰 문제를 작은 문제로 나눠서 푸는 알고리즘, 중복되는 작은 문제가 존재해 이에 대한 결과값을 저장해두어 계산 중복을 없애는 것.
- 1940년 Richard Bellman이 단지 이름이 멋있어보여서 사용하게됨.
- 한글로 '동적 계획법'이라고 불리는데, 이름은 아무의미없으니 이름에서 뜻을 찾지 말아라.

# 위 알고리즘을 이용한 문제해결시 필요한 요소
- 아래의 두가지 전제조건 만족해야함
- 중간 결과값 메모(Memoization)를 위한 '배열'이 필요함
# 이 유형의 문제해결 능력 향상을 위해서 필요한 것
- 어려워 보이지만 패턴을 가지기 때문에 문제들을 많이 풀어보면서 감을 잡는 것이 중요하다.

# 다이나믹 프로그래밍으로 문제를 풀기 위한 문제의 전제조건
1. Overlapping SubProblem
- 문제를 작은 문제로 쪼갤 수 있고,
- 큰 문제와 작은 문제를 같은 방법으로 풀 수 있으며,
- 중복되는 작은 문제가 존재해야 한다.

2. Optimal Substructure
- 문제의 정답을 작은 문제의 정답으로부터 구할 수 있으며,
- 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다.

# 피보나치 함수
- F0 = 0, F1 = 1, Fn = Fn-1 + Fn-2 (n>=2)

# Overlapping SubProblem 예시 : 피보나치 함수
- 문제를 작은 문제로 쪼갤 수 있고, -> 점화식을 보아 만족.
- 큰 문제와 작은 문제를 같은 방법으로 풀 수 있으며, -> 점화식을 보아 만족.
- 중복되는 작은 문제가 존재해야 한다. -> 색칠해둔게 중복되는 작은 문제이므로 만족.

문제 : N번째 피보나치 수를 구하는 문제
작은 문제 : N-1번째 피보나치 수를 구하는 문제, N-2번째 피보나치 수를 구하는 문제

문제 : N-1번째 피보나치 수를 구하는 문제
작은 문제 : N-2번째 피보나치 수를 구하는 문제, N-3번째 피보나치 수를 구하는 문제

문제 : N-2번째 피보나치 수를 구하는 문제
작은 문제 : N-3번째 피보나치 수를 구하는 문제, N-4번째 피보나치 수를 구하는 문제

# Optimal Substructure : 피보나치 함수
- 문제의 정답을 작은 문제의 정답으로부터 구할 수 있으며, -> 점화식을 보아 만족.
- 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다. -> 계산 중간에 필요한 4번째 피보나치 값은 항상 같은 값이므로 만족.

10번째 피보나치 수를 구하면서 구한 4번째 피보나치 수
9번째 피보나치 수를 구하면서 구한 4번째 피보나치 수
8번째 피보나치 수를 구하면서 구한 4번째 피보나치 수
...
5번째 피보나치 수를 구하면서 구한 4번째 피보나치 수

# 다이나믹 프로그래밍으로 문제 해결시 나타나는 효과
- 비효율적인 중복연산이 제거됨

# 다이나믹 프로그래밍을 적용한 피보나치 함수 코드
@ 다이나믹 프로그래밍 적용전
- 시간복잡도 : level이 N인 이진트리에 노드가 최대 몇개 존재할 수 있는지 보면 되므로 약 O(2^N)

#include <iostream>

using namespace std;

int cnt = 0; // 총 연산 횟수 출력을 위한 전역변수

int fibonacci(int n)
{
    if(n <= 1)
        return n;
    else{
        cnt++;
        return fibonacci(n-1) + fibonacci(n-2);  //f(n) = f(n-1) + f(n-2)
    }  
}

int main(void)
{
    cout << fibonacci(39) << endl;
    cout << cnt;                      // 39에 대한 값을 구하는데 102334154(1억) -> 1초가 간당간당 함
}

@ 다이나믹 프로그래밍 적용후
- 시간복잡도 : d 배열에 채워 넣어야하는 값의 개수 x 1칸을 채우는 복잡도 = O(N)
- 시간복잡도가 낮더라도 int형 배열은 +- 20억 까지만 담을 수 있으므로, 아래의 방법으로 약 fibonacci(75)까지만 구할 수 있음

#include <iostream>

using namespace std;

int cnt = 0;            // 총 연산 횟수 출력을 위한 전역변수

int d[100] = {0, 1};    // d[0] = 0, d[1] = 1, d[2~99] = 0

int fibonacci(int n)
{
    if(n <= 1)
        return d[n];
    
    else if(d[n] > 0)   // n>=2 일땐 d[n]이 0보다 크면 이미 계산된 값이 있는 것이므로 바로 결과값 반환(중복연산이 없어짐)
        return d[n];

    else
    {
        cnt++;
        d[n] = fibonacci(n-1) + fibonacci(n-2);    //f(n) = f(n-1) + f(n-2)
        return d[n];  
    }
}

int main(void)
{
    cout << fibonacci(70) << endl;
    cout << cnt;                               // 70번째 수를 구함에도 불구하고 103번의 연산밖에 안일어남
}

다이나믹 프로그래밍 문제를 푸는 두 가지 방법

* Top-Down, Bottom-Up 방식 모두 최종값이 결정되는 순서는 d[1], d[2], d[3],,, 순이다. (구현방식의 차이일 뿐)

1. Top-down
- 큰 문제를 점점 작게 만들어나갔다가 다시 되돌아오면서 푸는 방법

2. Bottom-up
- 작은 문제부터 풀면서 점차 큰 문제를 풀어나가는 방법

<Top-down 방식>

# (1) 구현 방법
-> '재귀호출' 방식으로 구현
1. 문제를 작은 문제로 나누어 맨 아래의 작은 문제까지 내려간다.
2. 맨 아래서부터 작은 문제를 풀며 점차 큰 문제를 풀며 다시 올라온다.

@ 피보나치 구현 예시(위에서 구현했던 방식)

int d[100] = {0, 1};    // d[0] = 0, d[1] = 1, d[2~99] = 0

int fibonacci(int n)
{
    if(n <= 1)
        return d[n];
    
    else if(d[n] > 0)   // n>=2 일땐 d[n]이 0보다 크면 이미 계산된 값이 있는 것이므로 바로 결과값 반환(중복연산이 없어짐)
        return d[n];

    else
    {
    	d[n] = fibonacci(n-1) + fibonacci(n-2);    //f(n) = f(n-1) + f(n-2)
        return d[n];  
    }
}

# (2) 시간복잡도 구하는 방법
= d 배열에 채워 넣어야하는 값의 개수 x 1칸을 채우는 복잡도
ex) 위의 피보나치 구하는 함수 예시
d 배열에 채워 넣어야하는 값의 개수 = N
1칸을 채우는 복잡도 = O(1), (fibonacci(n-1) + fibonacci(n-2) 에서 덧셈연산 1개 뿐이므로)
총 시간복잡도 = O(N)

<Bottom-up 방식>

# (1) 구현 방법
-> 'for문을 이용한 반복문'으로 구현
1. 문제를 크기가 작은 문제부터 차례로 푼다.
2. 문제의 크기를 조금씩 크게 만들면서 문제를 점점 푼다.

@ 피보나치 구현 예시('for문'을 이용함)

int d[100] = {0, 1};   // d[0] = 0, d[1] = 1, d[2~99] = 0

int fibonacci(int n)
{
    if(n <= 1)
        return d[n];

    else if(d[n] > 0)
        return d[n];

    else{
        for(int i = 2; i <= n; i++)
            d[i] = d[i-1] + d[i-2];

        return d[n];
    }
}

# (2) 시간복잡도 구하는 방법
= for문의 반복횟수

Top-down <-> Bottom-up 코드상의 차이

- for문 안에 있는 것들을 Top-Down 방식에서 n인자를 i인자로 수정해주고, 함수호출을 d로 변경해주면 Bottom-up 방식이 됨.

다이나믹 프로그래밍 문제풀이 전략

1. i번째 d인 d[i]에 어떤 값이 들어갈지 문장으로 정의해준다.
- 대부분의 다이나믹 문제는 문제에서 구하라는 값을 그대로 D[N]에 넣어주면 된다.
ex) 피보나치의 경우 d[i] = i번째 피보나치 수

2. d[i]에 대한 점화식을 찾는다.
ex) d[i] = d[i-1] + d[i-2]

3. Top-down 방식으로 해결하려는 경우 재귀 호출 인자의 개수를 생각한다.