동적 계획법(Dynamic Programming) 이해하기

동적 계획법을 이해하기 전에 필수로 재귀와 분할 정복을 이해하고 시작하길 바란다. 해당 기법들의 이해없이 바로 동적 계획법을 이해하기란 쉽지 않다.

동적 계획법이란

문제를 작은 부분 문제로 나누고, 그 부분 문제의 결과를 저장해 다시 사용함으로써 전체 문제를 효율적으로 해결하는 기법이다. 이 방법은 특히 중복되는 부분 문제를 가진 문제를 해결하는 데 유용하며, 재귀적으로 표현되는 문제를 최적화된 방식으로 풀 수 있다.

1.1 중복되는 부분 문제

동적 계획법은 큰 의미에서 문제를 작은 부분 문제로 나누고, 그 부분 문제를 합쳐 원래 문제를 해결한다는 관점에서 '분할 정복'과 같은 접근 방식을 가지고 있다.


하지만 두개 사이에는 차이가 존재하는 데, 바로 어떤 부분 문제가 여러번 계산되는 것을 저장을 통하여 피한다는 것이다. 아래 예시를 통해서 확인해보자.

예시 : 피보나치 수열

피보나치 수열은 수학적으로 다음과 같이 정의된다:

  - F(0) = 0
  - F(1) = 1
  - F(n) = F(n-1) + F(n-2) (n ≥ 2)

재귀로 풀어낸 피보나치 수열

#include <iostream>
using namespace std;

int fibo(int n) {
    if (n == 0 || n == 1) return n; // 기본 경우: F(0) = 0, F(1) = 1
    return fibo(n - 1) + fibo(n - 2); // 재귀 호출로 계산
}

int main() {
    int n = 10;
    cout << "피보나치 수열 결과 (완전 탐색, n = 10): " << fibo(n) << endl;
    return 0;
}

위의 코드는 재귀를 활용한 완전 탐색을 이용한 피보나치 수열을 구하는 문제이다.


이 함수는 재귀로 인하여 간단 명료하게 풀리지만 호출되는 함수를 생각해보면 중복되는 함수 호출이 많아 진다는 것을 알 수 있다.


이러한 비효율적인 호출이 n이 커질 수록 기하급수적으로 많아지며 문제 풀이에 문제가 생긴다.

n=5인 피보나치수열

위의 그림은 n=5일 때의 호출 스택을 그림으로 표현한 것이다. n이 매우 적은 수지만 이미 많은 중복호출을 보인다는 것을 볼 수 있다.

중복되는 함수들

fibo(1)와 fibo(0)는 기저 사례(base case)이기 때문에 제외한다고해도 n=5밖에 되지 않는데도 fibo(3)과 fibo(2)가 중복되어 호출되고 있다.

 

이러한 중복 호출을 막기 위해서 사용하는 것이 다이나믹 프로그래밍(DP)이며, fibo(3)과 fibo(2)를 미리 저장을 하여 다음에 그 함수가 호출되었을 때 저장한 값을 불러들이기만 한다면 더욱 효율적인 프로그램이 될 것이다.

DP 알고리즘을 사용했을 경우

fibo(3)과 fibo(2)의 중복 호출을 해결했더니 되게 간결한 호출 스택을 보이는 것을 볼 수 있다.


방금 위의 방식과 같이 각 문제의 답을 메모리에 저장하는 것을 메모이제이션(memoization)이라고 한다.


동적 계획법에서 사용하는 메모이제이션(meoization)을 사용하는 방법에 대해서 설명하겠다. 일단 아래의 코드를 확인하자.

1.2 중복 해결

메모이제이션(memoization)으로 풀어낸 피보나치 수열

#include <iostream>
using namespace std;

int cache[101]; // 최대 100까지의 값을 저장할 수 있는 배열

int fib_dp(int n) {
    if (n == 0 || n == 1) return n; // 기본 경우: F(0) = 0, F(1) = 1

    int& ret = cache[n];
    if (ret != -1) return ret; // 이미 계산된 값이 있으면 반환
    return ret = fib_dp(n - 1) + fib_dp(n - 2); // 값을 계산하고 저장
}

int main() {
    int n = 10;

    // cache 배열을 -1로 초기화
    for (int i = 0; i <= 100; i++) {
        cache[i] = -1;
    }

    cout << "피보나치 수열 결과 (DP, n = 10): " << fib_dp(n) << endl;
    return 0;
}

n이 최대 100까지 입력될 수 있다고 가정했을 때, DP를 사용한 피보나치수열에 대한 코드이다. 위에서 재귀를 이용한 피보나치에 대해 추가된 사항과 함께 이 함수를 설명해보겠다.

1. 캐시 배열(cache[101])

int cache[101]; // 최대 100까지의 값을 저장할 수 있는 배열

크기가 101인 정수 배열 cache를 선언한다. 이 배열은 피보나치 수열의 결과를 저장하는 데 사용되며, 최대 n=100까지 계산할 수 있도록 크기를 설정했다.

2. 캐시 배열 초기화

// cache 배열을 -1로 초기화
for (int i = 0; i <= 100; i++) {
    cache[i] = -1;
}

초기에는 모든 배열 값을 -1로 설정하여 아직 계산되지 않았음을 나타낸다. 이를 통해 이미 계산된 값을 구별할 수 있다. 또한 memset을 이용해서 배열을 초기화할 수 있으니 한번 시도해 보길 바란다.

3. 기저 사례(base case) 처리

if (n == 0 || n == 1) return n; // 기본 경우: F(0) = 0, F(1) = 1

피보나치 수열의 가장 기본적인 값 F(0)과 F(1)은 각각 0과 1로 정의된다. 따라서 n == 0이거나 n == 1일 때는 해당 값을 바로 반환한다.

4. 이미 계산된 값 처리

if (cache[n] != -1) return ret; // 이미 계산된 값이 있으면 반환

if (cache[n] != -1)에서, 만약 cache[n]에 이미 값이 저장되어 있다면, 그 값을 반환한다. 이렇게 하면 중복 계산을 방지할 수 있다.

5. 재귀 호출과 값 저장

return ret = fib_dp(n - 1) + fib_dp(n - 2); // 값을 계산하고 저장

아직 계산되지 않은 경우, fib_dp(n-1)과 fib_dp(n-2)를 재귀적으로 호출하여 값을 계산한 후, 그 결과를 cache[n]에 저장한다. 이렇게 함으로써 동일한 값이 다시 필요할 때 바로 반환할 수 있도록 한다.

 

1.3 메모이제이션(memoization) 구현 패턴

동적 계획법을 구현한다는 건 이 메모이제이션을 구현한다는 것과 같다. 그런 만큼 한 가지의 패턴을 정해두고 항상 같은 형태로 구현하는 것이 좋다. 한 가지 패턴을 정하고 구현한다면 작성하기도, 버그를 찾기도 쉬워지기 때문이다.

 

---

1. 항상 기저 사례(base case)를 제일 먼저 처리한다.

• 입력이 범위를 벗어난 경우 등을 기저 사례로 처리하면 유용하다. 기저 사례를 먼저 확인하지 않고 cache[]에 접근하면 범위를 벗어나는 등의 오류를 피할 수 있다.

2. 함수의 반환값을 고려해서 cache를 초기화해야 한다.

• 피보나치 수열의 반환값은 항상 > -1 이기 때문에 -1로 초기화한다. cache[]의 해당 위치에 적혀있는 값이 -1이라면 계산된 반환값이 없다는 것을 의미한다. 만약에 함수가 -1을 반환할 수도 있다면 -1로 초기화하는 방법은 적합하지 않다.

3. cache에 접근할 때, 참조형(reference)을 활용한다.

• 참조형 ret의 값을 바꾸면 cache[n]의 값도 변하기 때문에 답을 저장할 때도 매번 귀찮게 cache[n]을 적을 필요가 없다. 특히 다차원 배열일 때 매우 유용하다.

---

 

2.1 최적 부분 구조(Optimal Substructure)

동적 계획법을 사용할 수 있는가에 대해서 판단하기 위해서는 최적 부분 구조가 성립하는지도 확인해야 한다.
최적 부분 구조를 간단하게 설명하자면 재귀 호출을 통해서 큰 문제에서 작은 문제로 분할될 때, 작아진 문제로만 판단하여 최적의 답을 낼 수 있는 것이다.

 

간단한 예시를 들어서 설명하자면, 서울에서 부산까지 가는 최단 경로를 들 수 있다. 이 최단 경로가 대전을 지난다고 할때, (서울, 대전) 과 (대전, 부산)으로 나눈다고 한다.

 

최적 부분 구조의 예

위 그림에서 서울에서 부산으로 가는 최단 경로를 찾는다고 하면 (서울, 대전)과 (대전, 부산) 각각의 최단 경로인 10과 5를 선택하면 찾을 수 있다.


이렇게 각 부분의 최선의 선택이 전체의 최선의 선택으로 이어지기 때문에 최적 부분 구조를 갖는다고 할 수 있다.

 

하지만 작은 문제의 최적의 선택만으로는 전체 문제의 최적의 선택을 구할 수 없다면 해당 문제에는 최적 부분 구조가 존재하지 않는다고 할 수 있다.

최적 부분 구조가 될 수 없는 예

해당 그림에서 돈의 합이 2만원 이하의 경로를 찾는다고 하면, (대전, 부산)으로 가는 경로 중에 (2시간, 2만원)으로 가는 경로밖에 선택하지 못 한다.


따라서 이 문제는 작은 문제(대전, 부산)에서 최선의 선택인 (1시간, 2만원)을 골른다면 돈의 합이 3만원이 되기 때문에 전체 문제인 (서울, 부산)을 풀 수 없다.

2.2 예시 : 최장 증가 부분 수열(LIS)

최장 증가 부분 수열(LIS)란? 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이다. 즉, 배열에서 증가하는 수열이 가장 긴 것을 고르면 된다.


예를 들어,
S = { 1, 3, 4, 2, 4 } 라고 하면 '1 2 4'는 S의 증가 부분 수열이지만, '1 4 4'는 그렇지 않다.

완전 탐색부터 시작하기

숫자를 하나씩으로 조각을 낸 뒤, 한 조각에서 숫자 하나씩을 선택하는 완전 탐색 알고리즘을 만들어 보자.

수열의 예시

위와 같은 수열이 있다고 가정한다. 수열의 A[1]에서 LIS를 만든다고 하면 어떻게 해야할까? 그러면 A[1]의 값인 2보다 큰 것을 고르고 재귀 호출을 시키게 되면 이것이 반복되면서 LIS를 만들 수 있다.

 

즉, A[j] 에서의 LIS는 A[j+1 ... n] 에서 만들어진 LIS와 A[j]를 합치면 A[j]의 LIS가 만들어진다는 것이다. 만약에 이것이 이해가 안된다면 재귀를 완전히 이해하지 못한 것이다.

A[1]일 때, 골라야하는 숫자들

파란색 칸의 숫자들을 재귀해서 만들어지는 수열 중 가장 긴 것을 선택해서 A[1]에 붙이면 A[1]에서 시작하는 LIS가 만들어지는 것을 확인할 수 있습니다.

완전 탐색으로 풀어낸 LIS

int lis(const vector<int>& A) {
    // 기저 사례: A가 텅 비어 있을 때
    if (A.empty()) return 0;

    int ret = 0;
    for(int i = 0; i < A.size(); ++i) {
        vector<int> B;
        for(int j = i+1; j < A.size(); ++j)
            if(A[i] < A[j])
                B.push_back(A[j]);
        ret = max(ret, 1 + lis(B));
    }
    return ret;
}

👇 코드 설명

1. 기저 사례 (Base Case):

   if (A.empty()) return 0;

• 리스트 A가 비어 있으면 0을 반환한다. 더 이상 탐색할 수 있는 값이 없음을 의미한다.

2. 반환값 초기화:

   int ret = 0;

• 결과값을 저장할 변수를 0으로 초기화한다. 이 변수는 최대 증가 부분 수열의 길이를 저장한다.

3. 리스트 순회:

   for(int i = 0; i < A.size(); ++i)

• 리스트 A를 처음부터 끝까지 탐색한다. 각 인덱스 i를 기준으로 그 이후의 값을 탐색한다.

4. 부분 수열을 만들기 위한 리스트 B 생성:

   vector<int> B;
   for(int j = i+1; j < A.size(); ++j)
       if(A[i] < A[j])
           B.push_back(A[j]);

• 현재 인덱스 i 이후의 값들을 탐색하며, A[i]보다 큰 값을 찾아 리스트 B에 추가한다. 이는 증가하는 부분 수열을 찾기 위한 과정이다.

5. 재귀 호출 및 결과 갱신:

   ret = max(ret, 1 + lis(B));

• B에 대해 다시 lis() 함수를 재귀적으로 호출하고, 그 결과에 1을 더해 ret 값을 갱신한다. 이는 현재 요소를 포함한 LIS의 길이를 계산하는 과정이다.

6. 최종 결과 반환:

   return ret;

• 최종적으로 LIS의 최대 길이를 반환한다.

 

최적 부분 구조(Optimal Substructure)로 풀어보기

위의 코드를 메모이제이션을 바로 적용하기에는 입력 방식이 배열이기 때문에 cache에 저장시키기 까다롭다. 이 입력을 최적 부분 구조를 쓸 수 있게 바꾸어 보자.

 

우리가 앞서 (서울, 부산)의 최단 경로를 찾을 때, (서울, 대전) 과 (대전, 부산)에서 각각 최단 거리를 찾으면 (서울, 부산)의 최단 거리를 구할 수 있다는 사실을 알 수 있었다. 이 말은 (서울, 대전)의 최단 거리는 (대전, 부산)의 최단 거리를 구하는 것과 서로 독립적이라는 말이다.

 

해당 문제에도 이 논리를 적용할 수 있다. A[j]와 lis(A[j+1 ... n])  서로 독립적이며, 각각의 최대치를 찾기만 한다면 수열 A의 LIS를 구할 수 있다. 즉, lis(A[0 .. j]) 의 값은 lis(A[j+1 ... n]) 을 구하는 데 필요하지 않다. 각 부분 문제마다 최대 길이만 찾으면 되는 것이다. 

최적 부분 구조를 이용한 LIS

#include <iostream>
#include <cstring> // memset 사용을 위한 헤더 파일
#include <algorithm>
using namespace std;

int n; // 수열의 길이
int cache[100], A[100]; // 캐시와 수열 배열

// A[start]에서 시작하는 증가 부분 수열 중 최대 길이를 반환하는 함수
int lis(int start) {
    int& ret = cache[start]; // 캐시 배열을 참조형으로 접근

    if (ret != -1) return ret; // 이미 계산된 값이 있으면 반환

    ret = 1; // A[start]는 반드시 포함되므로 길이 1로 시작

    for (int next = start + 1; next < n; ++next) {
        if (A[start] < A[next]) // 증가하는 부분 수열인지 확인
            ret = max(ret, lis(next) + 1); // 최대 길이 갱신
    }

    return ret; // 계산된 길이 반환
}

int main() {
    // 입력 예시: n=6, 수열 A = {5, 6, 7, 1, 2, 8}
    n = 6;
    A[0] = 5; A[1] = 6; A[2] = 7; A[3] = 1; A[4] = 2; A[5] = 8;

    // 캐시 배열을 -1로 초기화 (아직 계산되지 않은 상태)
    memset(cache, -1, sizeof(cache));

    int maxLen = 0; // 최대 증가 부분 수열의 길이를 저장하는 변수

    // 모든 시작점에서 LIS 길이를 계산하여 최댓값을 찾는다.
    for (int begin = 0; begin < n; ++begin)
        maxLen = max(maxLen, lis(begin));

    // 결과 출력
    cout << "최대 증가 부분 수열의 길이: " << maxLen << endl;

    return 0;
}

코드 설명

1. 캐시와 입력 배열 선언

   int n;
   int cache[100], S[100];

• n은 수열의 길이를 저장하는 변수다.
• cache[] 배열은 이미 계산된 값을 저장하는 캐시 배열이다.
• S[] 배열은 입력 수열을 저장한다.

 

2. 참조형을 사용한 캐시 접근

   int& ret = cache[start];

• 캐시의 start 인덱스 값을 참조형 ret으로 설정한다.
• 이를 통해 값을 저장할 때 cache[start] 대신 ret에 직접 값을 저장하거나 불러올 수 있다.

 

3. 이미 계산된 값 처리

   if (ret != -1) return ret;

• cache[start]에 값이 이미 저장된 경우, 즉 -1이 아닌 경우 해당 값을 반환한다. 이렇게 중복 계산을 방지한다.

 

4. 기저 사례 처리

   ret = 1;

• 현재 수열에서 S[start]는 존재하기 때문에 최소 길이는 1로 설정한다.

 

5. 다음 요소 탐색을 위한 반복문

   for(int next = start+1; next < n; ++next)

• start 이후의 인덱스를 탐색하여 증가하는 부분 수열을 찾기 위한 반복문이다.

 

6. 수열의 증가 여부 검사 및 재귀 호출

   if(S[start] < S[next])
       ret = max(ret, lis2(next) + 1);

• S[start]보다 큰 값을 가진 S[next]를 찾은 경우, 재귀적으로 lis2(next)를 호출하여 최대 길이를 갱신한다.

 

7. 최종 결과 반환

   return ret;

• 재귀 호출이 끝난 후, 계산된 LIS의 길이를 반환한다.

 

2.3 최적화 문제 동적 계획법 구현 패턴

메모이제이션의 구현패턴과 같이 일정한 패턴을 가지고 최적화 문제를 구현하는 것이 좋다. 물론 이 패턴이 모든 문제에 활용할 수 있는 것은 아니지만, 익숙해지기 위해 어떤 식으로 생각해야할 지 대략적인 지침은 될 것 이다.

---

 

1. 모든 답을 만들어 보고 그 중 최적해의 점수를 반환하는 완전 탐색 알고리즘을 만든다.
2. 전체 답의 점수를 반환하는 것이 아닌, 앞으로 남은 선택들에 해당하는 잠수만을 반환하도록 부분 문제 정의를 바꾼다.
3. 재귀 호출의 입력에 이전의 선택에 관련된 정보가 있다면 꼭 필요한 것만 남기고 줄인다. 최적 부분 구조가 성립한다면 이전 선택에 관련된 정보를 완전히 없앨 수 있다. 여기서 우리의 목표는 최대한 최적 부분 구조가 가능한 구조로 만드는 것이다.
4. 입력이 배열이거나 문자열인 경우에 가능하다면 적절한 변환을 통해 메모이제이션을 하도록 한다.
5. 메모이제이션을 적용한다.

 

---

 

3. 결론

재귀 ▶️ 메모이제이션 ▶️ 완전 탐색 ▶️ 최적화 부분 문제 순으로 동적 계획법이 어떻게 활용되는지 확인했다. 동적 계획법은 복잡한 문제를 효율적으로 해결하는 매우 강력한 도구다. 이 글에서는 동적 계획법의 개념과 이를 적용한 문제들에 대해 설명하였다. 이항 계수, LCS, LIS와 같은 문제들은 모두 동적 계획법을 사용해 빠르게 해결할 수 있으며, 이를 통해 반복되는 계산을 줄이고 성능을 크게 향상시킬 수 있다.