[DP] 다이나믹 프로그래밍

개념

큰 문제를 작은 문제로 나눠서 풀고, 다시 원래 큰 문제를 푸는 알고리즘

Dynamic Programming이라는 이름은 그냥 멋있어서 붙혀졌다고 합니다.

큰 문제를 작은 문제로 나눠서 푸는 두 개의 알고리즘

DP : 작은 문제가 여러번 나온다. 여러번 나오는 문제의 정답이 항상 같다는 것을 이용해 각각의 문제를 한 번씩 푼다.
분할 정복 알고리즘 : 모든 작은 문제가 한 번씩 나와서 그냥 모든 문제를 한 번씩 푼다.

DP의 두가지 속성

1. Overlapping Subproblem : 부분 문제가 겹친다. 부분 문제를 여러번 구해야하는 경우가 발생한다.
2. Optiaml Substructure : 부분 문제의 정답이 항상 같다. 작은 동일한 문제가 나오면 이 두 문제의 정답은 항상 같아야 한다. 따라서 부분 문제의 값을 저장해어서 실행시간을 줄인다.

Overlapping Subproblem

피보나치 수

$F_{0} = 0$
$F_{1} = 1$
$F_{n} = F_{n-1} + F_{n-2}$

1. 크기 n 문제를 n-1과 n-2 문제로 나워서 풀고 이들을 더해서 큰 문제를 푼다.
2. 다음으로 작은 문제들이 겹치는지를 체크
3. n-1 문제를 풀 때 n-2와 n-3을 구해야 함
4. n-2 문제를 풀 때 n-3와 n-4을 구해야 함
5. n-3 문제가 중복해서 발생함.
6. 즉, 큰 문제를 작은 문제로 쪼갤 수 있고 큰 문제와 작은 문제를 푸는 방법이 같다.

Optiaml Substructure

문제의 정답을 작은 문제의 정답에서 구할 수 있다. 1

서울에서 부산갈 때 제일 빠른 길 (가정): 서울 -> 대전 -> 대구 -> 부산
대구에서 부산갈 때 제일 빠른 길 : 대전 -> 대구 -> 부산
알고보니 울산도 갈 수 있는 도시였다고 할 때,
대구에서 부산갈 때 제일 빠른 길 : 대전 -> 울산 -> 부산 으로 바뀌었다. 이런 경우는 없음. 즉, 큰 문제의 정답을 구할 때 작은 문제의 정답이 꼭 사용 되어야한다.

10 번째 피보나치 수를 구하면서 4번째 피보나치 수를 구해야한다.
9 번째 피보나치 수를 구하면서 4번째 피보나치 수를 구해야한다.
4 번째 피보나치 수를 구하면서 4번째 피보나치 수를 구해야한다.
4 번째 피보나치 수는 변하지 않는다.

-> 한 번 작은 문제를 풀어두고 이 문제의 정답을 어디에 저장해두자!

피보나치 수

메모를 하지 않는다면, 시간 복잡도 $O(2^{n})

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

메모를 한다면, 시간 복잡도는 $O(N)$

int memo[100];
int fibo(int n){
    if(n <= 1){
        return n;
    }else{
        if(memo[n]> 0){
            return memo[n];
        }
        memo[n] =  fino(n-1) + fibo(n-2);
        return memo[n];
    }
}

시간 복잡도

모든 문제는 한 번씩만 푼다. 함수 호출은 n번 이루어 진다. 함수 호출은 메모에 적혀있지 않아서 메모를 구하는데 사용되는 호출을 의미한다. 즉, 함수 호출 시간은 $O(1)$이 걸린다. 따라서 전체 시간 복잡도는 $O(n)$이다.

다이나믹을 푸는 두 가지 방법

Top-down : 재귀함수

큰 문제를 점점 쪼개면서 작은 문제로 가는 것. 이전에 했던 방법.

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

Bottom-up : for문

작은 문제가 점점 합쳐지면서 큰 문제를 풀게 되는 것

1. 문제를 크기가 작은 문제부터 차례대로 푼다.
2. 문제의 크기를 조금씩 크게 만든다.
3. 작은 문제를 풀면서 왔기 때문에 큰 문제는 항상 풀 수 있다.

int d[100];
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];
}

? Bottom-up?

대부분 Top-down으로도 Bottom-up으로도 풀 수 있다. 전자가 stack에 넣고 빼야해서 느릴 수도 있고, 후자가 전자는 필요없는 모든 경우를 다 풀어야해서 느릴 수도 있다. 일반적으로 뭐가 더 좋은지는 정해져있지 않고, 전자와 후자로 풀 떄 모두 시간 복잡도는 같게 나올 것이다.

문제 풀이 전략 1 : Bottom-up

1. 문제를 크기가 작은 문제부터 차례대로 푼다.
2. 문제의 크기를 조금씩 크게 만든다.
3. 작은 문제를 풀면서 왔기 때문에 큰 문제는 항상 풀 수 있다.

답을 구하는 점화식을 정의하고, 점화식을 코딩한다.

1. D[N]을 구해야한다는 것을 정한다.
2. N을 N-1과 N-2로 나누는 법을 생각한다.
3. D[N] = D[N-1] + D[N-2]를 짠다.

문제 풀이 전략 2 : Top-down

1. 문제에서 구하고자 하는 답을 문장으로 나타낸다.
2. EX ) N 번째 피보나치 수
3. Bottom-up : 이제 이 문장에 나와있는 변수의 갯수만큼 메모하는 배열을 만든다.
4. Top-Down : 이제 이 문장에 나와있는 변수의 갯수 = 재귀호출 인자의 갯수
5. 문제를 작은 문제로 나누고, 수식을 이용해서 문제를 표현해야 한다.