[알고리즘] C++로 이해하는 동적 프로그래밍

참고 : 알고리즘 문제 해결 전략

---

☑️ C++로 이해하는 동적 프로그래밍

동적 프로그래밍(Dynamic Programming)을 부르는 정확한 언어는 동적 계획법이다. 단어는 최적화 문제를 연구하는 수학 이론에서 왔기에 전산학에서 말하는 Dynamic, 혹은 Programming과는 연관이 없다. 하지만 블로그에 작성할 때는 나에게 익숙한 동적 프로그래밍으로 올린다.

동적 프로그래밍은 복잡한 문제를 작은 하위 문제로 분할하여 해결하는 알고리즘 설계 방법을 의미한다. 이 방법은 분할 정복과 같은 접근 방식을 가진다. 하위 문제의 해결책을 저장하고 재사용함으로서 계산의 효율성을 높인다. 이때 이미 계산한 값을 저장해 두는 메모리의 장소를 캐시(cache)라고 부르며, 두 번 이상 계산하는 부분 문제를 중복되는 부분 문제(overlapping subproblems)라고 부른다.

 

1️⃣ 헷갈리는 분할 정복과 동적 프로그래밍의 차이점

동적 프로그래밍과 분할 정복(divide and conquer)은 모두 문제를 작은 부분 문제로 나누어 해결하는 접근 방식을 가진다. 이 두개의 차이점은 독립과 중복의 차이점에 있다.

 

분할 정복은 작은 부분 문제로 나누었을 때, 각각 해결하고 결과를 병합한다. 하지만, 동적 프로그래밍은 작은 부분 문제들을 해결하고 해답을 저장한 후에 재사용함으로서 반복적인 계산을 피하게 된다.

왼쪽의 트리는 분할 정복을 보여준다. 왼쪽 트리의 부분 문제들은 서로 연관이 없기 때문에 해당하는 부분 문제의 해답만을 구한다. 오른쪽의 트리는 동적 프로그래밍을 나타내는데 중복되는 부분 문제가 있다. 123456은 345678과 3456을 공유한다. 각자 계산을 한다면 총 2번의 계산이 필요하다. 동적 프로그래밍에서는 3456의 값을 저장하고 똑같은 문제의 계산이 필요할 때 이전에 계산한 값을 재활용하는 식이다.

 

피보나치 수열이 중복 부분 문제의 전형적인 예시를 가진다.

 

2️⃣ 메모이제이션 (Memoization)

위 사진에서 우측 트리를 설명하면서 값을 저장하고 재활용하는 방법을 메모이제이션이라고 한다. 메모이제이션은 동적 프로그래밍의 핵심 기법으로 계산 결과를 메모리에 저장하고 동일한 계산을 반복하지 않도록 한다. 이를 통해서 동일한 문제를 한 번만 계산한다는 것을 보장한다.

 

📌 메모이제이션 구현

동적 프로그래밍은 알고리즘 문제 중에 흔한 유형 중 하나이기 때문에 한 가지 패턴을 정해두고 메모이제이션을 구현해두면 효율적이다. 아래의 피보나치 수열을 구하는 코드에서 메모이제이션의 구현을 살펴보자.

vector<int> memo(n + 1, -1);

메모이제이션을 담당한 변수를 선언한다.

 

if (memo[n] != -1) {
    return memo[n];
}

memo[n]의 값이 초기 값인지 확인하고 아니라면 그대로 반환한다.

 

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

int fibonacci(int n, vector<int>& memo) {
    if (n <= 1) return n;

    if (memo[n] != -1) {
        return memo[n];
    }

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

int fib(int n) {
    vector<int> memo(n + 1, -1);
    return fibonacci(n, memo);
}

int main(void) {
    int num;
    cin >> num;

    cout << fib(num) << endl;
    return 0;
}

메모이제이션을 구현한 피보나치 수열을 구하는 코드는 위와 같다.

 

📌 메모이제이션 장/단점

메모이제이션을 사용하면 계산 중복을 피할 수 있고 시간 복잡도를 효율적으로 개선할 수 있다. 하지만, 캐시에 모든 부분 문제의 결과를 저장하기 때문에 메모리 사용량이 많아질 수 있다.

 

3️⃣ 동적 프로그래밍에 접근하기

동적 프로그래밍의 개념을 이해하는 것과 실제 문제에 적용하는 것은 별개의 일이다. 동적 프로그래밍 문제를 해결하기 위해서는 역설적으로 많은 동적 프로그래밍 문제를 풀어보면서 패턴을 인식하고 적용하는 능력을 길러가야 한다. 다른 개념에 비해서 많은 풀이와 경험이 필요하다.