(공사중) 동적 계획법, 다이나믹 프로그래밍 (공사중)

1. 개요

동적 계획법 (Dynamic Programming, 이하 DP)는 메모리를 적절히 사용하여 알고리즘의 수행 시간 효율성을 비약적으로 향상시키는 방법입니다.

 

이미 계산된 결과를 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 하는 것이죠.

 

예를 들어서 '피보나치 수열' 의 예시를 봅시다.

 

 

피보나치 수열은 위와 같은 점화식으로 나타낼 수 있으며

이를 가장 간단하게 구현하는 방법은 재귀를 사용하는 겁니다.

 

 

이런 식으로 말이죠.

 

그런데 잘 살펴보면 

피보나치 수열을 재귀로 구현하면 상당히 비효율적인 코드 진행을 보입니다.

 

피보나치 수열 알고리즘을 재귀 함수로 표현한 경우를 상태 트리로 나타내면 위와 같습니다.

 

이 상태 트리를 보면 알 수 있듯

이미 계산된 값을 또 계산하고 있는 것을 볼 수 있습니다. 

Fibo(3) 에 대한 결과는 이미 계산하였는데, 우측 좌측트리에서 Fibo(3)을 한 번 더 계산하고 있죠?

 

위와같은 피보나치 수열은 재귀 호출에 의해 함수가 계속 분기됩니다.

그렇기에 O(2^n) 이라는 파멸적인 시간복잡도를 가지고 있죠.

 

n = 40만 되더라도 매우 매우 많고 중복된 계산을 거듭합니다.

속도도 느리고 비효율적이라고 할 수 있죠.

 

앞서 말했던 문장중에 기억하시나요?

 

이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다.

 

이것이 DP의 핵심입니다.

 

위 피보나치 수열을 DP 형식으로 풀어내면 다음과 같습니다.

 

계산 결과를 따로 선언한 큰 메모리에 저장해가면서

중복 계산을 막기위해 이미 계산한 값은 메모리에서 빼서 사용하는 것이죠.

이 코드의 시간복잡도는 O(N) 입니다. 엄청난 차이죠?

 

이런 방법은 메모이제이션 이라고 합니다.

메모이제이션은 한 번 계산한 결과를 메모리 공간에 메모하는 기법이라고 정의할 수 있으며, 마치 캐싱과 유사하게 동작합니다. 

 

2. 다이나믹 프로그래밍을 사용할 수 있는 조건

다이나믹 프로그래밍은 문제가 다음의 조건을 만족할 때 사용할 수 있습니다.

1. 최적 부분 구조

  -> 문제가 작은 공통된 부분 문제의 집합이고 큰 문제를 작은 문제로 분할할 수 있으며

       작은 문제의 답을 모아서 큰 문제를 해결할 수 있을 경우

        (마치 분할정복과 유사한 아이디어 입니다.)

 

2. 중복되는 부분 문제

  -> 동일한 작은 문제를 반복적으로 해결해야 하고, 중복된 계산이 존재할 경우

 

 

* 분할정복 vs 다이나믹 프로그래밍

둘 다 최적 부분 구조를 띄고 있지만, DP는 부분 문제가 중복된다는 조건이 하나 더 필요합니다.

DP 문제에서는 각 부분 문제들이 서로 영향을 미치고 부분 문제가 중복됩니다.

그러나 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않습니다.

(퀵 소트나 병합 정렬의 경우를 잘 생각하시면 무슨 의미인지 알 수 있습니다.)

 

3. 문제 접근법

1. 탑다운 방식

탑다운 방식은 하향식이라고도 합니다.

앞서 선보였던 방식이 하향식 방식입니다.

 

 

예를들어 피보나치 Fibo(50)의 값을 구해야 한다면,

Fibo(50) = Fibo(49) + Fibo(48)

Fibo(49) = Fibo(48) + Fibo(47)

Fibo(48) = Fibo(47) + Fibo(46) ...

 

이런 식으로 위에서 아래로 내려가는 방식을 의미합니다.

보통 함수의 재귀호출을 통해서 많이 구현하기 때문에

구현의 난이도는 쉬울지라도 속도면에서 조금 떨어질 수 있습니다.

그렇기에 DP는 이후에 설명할 바텀-업 방식을 더욱 많이 사용합니다.

 

 

2. 바텀업 방식

바텀업 방식은 상향식이라고도 합니다. 

보통 DP의 전형적인 형태는 보텀업 방식입니다.

 

 

이런 식으로 dp[1] 부터 dp[num] 까지

아래서 위로 올라가면서 값을 구하는 방식을 바텀업 방식이라고 합니다.

 

이 방법이 속도가 훨씬 빠르기 때문에 실제 문제를 해결함에 있어 효율적일 수 있습니다.

 

 

3. 문제를 만났을 때 전략

1) 주어진 문제가 그리디, 구현, 완전 탐색, 백트래킹 등의 아이디어로 해결할 수 있는지 먼저 검토한다음, 다이나믹 프로그래밍을 고려하도록 합니다.

 

2) 보통 시간 제약이 빡빡한 문제일 경우 다이나믹 프로그래밍을 사용하는 경우가 많습니다.

 

3) 재귀 함수를 이용해서 비효율적인 프로그램을 작성한 뒤에 '탑 다운'으로 개선하는 방법을 사용하거나,

수학적인 점화식을 잘 고려하여 바텀 업으로 문제를 해결할 수 있습니다.

 

4) 점화식을 구해보자!

DP 문제의 경우 이미 구한 답을 통해서 다음 답을 도출해내는 아이디어를 채용하기 때문에 점화식을 구할 수 있다면 문제를 빠르게 해결할 수 있습니다.

 

 

4. 풀어볼 문제

https://www.acmicpc.net/problem/2193

#include <iostream>
using namespace std;

long long Solution(int len, int lastDigit) {
    if (len == 1) {
        return lastDigit == 1 ? 1 : 0;
    }

    long long count = 0;
    if (lastDigit == 0) {
        // If the last digit is 0, the next digit can be either 0 or 1
        count = Solution(len - 1, 1) + Solution(len - 1, 0);
    } else {
        // If the last digit is 1, the next digit must be 0
        count = Solution(len - 1, 0);
    }

    return count;
}

int main() {
    int N;
    cin >> N;

    // Start the recursion from the length N with the last digit being either 0 or 1
    long long result = Solution(N, 1) + Solution(N , 0);

    cout << result << endl;

    return 0;
}

 

#include <iostream>
#include <vector>
using namespace std;

vector<vector<long long>> dp(2, vector<long long>(91, -1));

long long Solution(int len, int num) {
    if (len == 1) {
        return num == 1 ? 1 : 0;
    }

    if (dp[num][len] != -1) {
        return dp[num][len];
    }

    long long count = 0;
    if (num == 0) {
        count = Solution(len - 1, 1) + Solution(len - 1, 0);
    }
    else if (num == 1) {
        count = Solution(len - 1, 0);
    }

    dp[num][len]= count;
    return count;
}

int main() {
    int N;
    cin >> N;

    long long result = Solution(N, 1) + Solution(N , 0);

    cout << result << endl;

    return 0;
}

 

#include <iostream>
#include <vector>
using namespace std;

vector<vector<long long>> dp(2, vector<long long>(91, 0));

int main() {
    int N;
    cin >> N;

    dp[1][1] = 1;
    dp[0][1] = 0;

    for (int i = 2; i <= N; i++)
    {
        dp[0][i] = dp[1][i - 1] + dp[0][i - 1];
        dp[1][i] = dp[0][i - 1];
    }

    cout << dp[0][N] + dp[1][N];
 

    return 0;
}

 

https://www.acmicpc.net/problem/11727