동적 계획법(Dynamic Programming, DP)

이 포스트는 국민대학교 소프트웨어학부 '알고리즘' 강의를 듣고 요약하는 포스트입니다. 원하시는 정보가 없을 수도 있습니다. 이 점 유의 바랍니다. 오류 지적은 매우 환영합니다!

---

동적 계획법

동적 계획법은 분할 정복 기법으로 문제를 해결하는 방식과 유사합니다. 분할 정복 기법에 대해 모르시는 분들은 제가 저번에 적은 포스트를 참고하셔도 됩니다.

2022.10.17 - [개념 정리/알고리즘] - 분할 정복 기법(Divide & Conquer)

 

동적 계획법도 하나의 문제를 여러 작은 문제들로 나눈 다음, 각 문제들의 해답을 이용해서 원래 문제의 답을 구합니다. 분할 정복 기법과의 차이점은 여러 작은 문제들의 연관성입니다.

예를 들어, 병합 정렬이나 퀵 정렬을 구현할 때 나눠지는 배열들은 서로 상관이 없습니다. 자기 배열 안에서 정렬이 이루어지기 때문에 다른 배열을 볼 필요도 없습니다. 병합 정렬은 두 배열을 합치는 과정이 있기는 하지만 중요하게 봐야 할 점은 나눠진 배열들이 자기 안에서 정렬되는 과정에서 다른 배열을 쳐다보지도 않는다는 점입니다.

2022.10.20 - [개념 정리/알고리즘] - 병합 정렬(Merge Sort)

2022.10.23 - [개념 정리/알고리즘] - 퀵 정렬(Quick Sort) (with Hoare)

 

피보나치 수를 구할 때는 나눠진 작은 문제들이 서로 연관이 있습니다. 아래 그림을 봅시다.

4번째 피보나치 수를 구하는 과정

2번째 피보나치를 구하는 과정이 왼쪽 서브 트리와 오른쪽 서브 트리에 중복됩니다. 4번째 피보나치 수를 구하기 위해 2번째 피보나치 수를 2번 계산해야 하는 번잡함이 생깁니다. 만약 100번째와 같이 큰 수를 찾았다면 98번째 수는 2번, 97번째 수는 3번, 96번째 수는 4번,... 이런 식으로 중복되는 연산의 수가 많이 늘어났을 것입니다. 이러한 문제를 해결하기 위해 피보나치 수를 구하는 문제를 동적 계획법에 따라 방법을 세워 봅시다.

Memoization(기억하기)

피보나치 수를 구하다가 맞이한 문제는 중복되는 연산이 너무 많아진다는 점이었습니다. 이를 해결하기 위해 하나의 아이디어가 나왔습니다.

이미 계산한 수는 어딘가에 저장하면 되지 않을까?

이때 적용할 수 있는 동적 계획법 중 하나로 memoization 기법을 적용합니다. 이 기법은 재귀를 이용한 기법입니다.

먼저 피보나치 수를 구하는 식에 따라 n - 1번째 수와 n - 2번째 수로 재귀적으로 들어갑니다. n - 1번째 또는 n - 2번째 피보나치 수가 이미 구해진 결과라면 그 결과를 그대로 반환합니다. 구해지지 않은 결과이면 구해진 결과가 나올 때까지 재귀적으로 들어갑니다. 이렇게 재귀적으로 내려가면 base case일 때까지 오게 됩니다. Base case에 대한 해답은 배열 같은 곳에 미리 저장해둡니다. 이를 C++ 코드로 구현하면 아래와 같습니다.

#include <iostream>
using namespace std;

#define _MAX_SIZE_ 1001
int fibNumbers[_MAX_SIZE_];

int fib(int);

int main()
{
    for (int i = 0; i <= _MAX_SIZE_; i++)
    { fibNumbers[i] = -1; }
    
    int result = fib(10);
    cout << result << endl;
    return 0;
}

int fib(int n)
{
    // 이미 구한 수인 경우 저장해둔 결과를 반환
    if (fibNumbers[n] > -1) { return fibNumbers[n]; }
    else if (n <= 1)    // Base case에 대한 정답 값을 저장
    {
        fibNumbers[n] = n;
        return n;
    }
    else
    {   // 재귀적으로 답을 찾아가는 과정
        fibNumbers[n] = fib(n - 1) + fib(n - 2);
        return fibNumbers[n];
    }
}

Bottom-Up 버전

위에서 설명한 Memoization도 동적 계획법 중 하나이지만 실제로 DP로 풀 때는 재귀적인 과정이 거의 없습니다. Top-Down 방식이 아닌 Bottom-Up 방식으로 문제를 해결해 나갑니다. 즉 작은 문제들로부터 시작해서 이 답들로 원래 문제의 답을 얻는 과정을 거칩니다. 위의 피보나치 수를 구하는 방법을 Bottom-Up 방식으로 바꾸면 아래와 같습니다.

int fib(int n)
{
    fibNumbers[0] = 0; fibNumbers[1] = 1;
    for (int i = 2; i <= n; i++)    // 작은 문제들의 해답들로 큰 문제의 해답을 얻어가는 과정
    { fibNumbers[i] = fibNumbers[i - 1] + fibNumbers[i - 2]; }
    
    return fibNumbers[n];
}

 

동적 계획법 과정

동적 계획법은 주로 최적화 문제를 해결할 때 많이 사용되는 방법입니다. 예를 들어, 특정 조건이 최대 또는 최소가 되는 해답을 원하는 문제들이 최적화 문제라 볼 수 있습니다. 이런 문제를 접할 때 동적 계획법을 생각하는 과정은 아래와 같습니다.

1. 해답의 구조 분석: 최적의 값을 어떻게 구할 수 있는지 분석
2. 재귀식 정의: 최적의 값을 얻을 수 있는 방법을 재귀식으로 정의
3. Bottom-Up 계산: 얻어낸 재귀식으로 상향식(bottom-up)으로 최적 값을 계산
4. 최적의 해답 계산: 3번은 값을 구한다면 이 단계에서는 해답을 계산

1번 과정에서 많은 사람들이 어려움을 겪습니다.(저도 그렇습니다.) 이 과정에서 주로 working backward 기법으로 분석하지만 저희는 working forward에 익숙하기 때문입니다. 예를 들어 바닥에 타일을 배열하는 경우의 수를 계산하는 문제가 있다고 합시다. 실제로 '2 X n 타일링'이라는 유명한 DP 문제가 있습니다.

[백준] 2 x n 타일링 문제: https://www.acmicpc.net/problem/11726

사람들은 일반적으로 아무것도 없는 맨바닥에서 타일을 하나씩 놓아보면서 총 몇 가지의 경우가 가능한지 생각합니다. 이러한 사고 과정을 working forward 과정이라 합니다. working backward는 이와 반대로 생각합니다.

어찌 됐든 바닥에 타일이 다 채워져 있을 때, 타일을 하나씩 뺄 때 남아있는 타일들은 어떤 형태가 나타날 것인가?

이런 식으로 이미 해결됐을 때 하나의 경우씩 빼보면서 문제의 해답을 어떻게 얻을 수 있을지 생각합니다. 이런 식으로 문제를 분석해서 얻어낸 최적 값을 얻는 방법을 재귀식으로 정의합니다. 아직 감이 잘 안 잡히시는 분들은 타일링 문제를 직접 풀어보시거나 풀이를 적어 놓은 블로그를 찾아서 읽어보시면 이해되실 겁니다.

그리고 3번 과정은 거스름 돈을 줄 때 줄 수 있는 최소의 동전 개수와 같은 해답을 찾아가는 과정이고 4번 과정은 거스름 돈을 줄 때 줄 수 있는 최소 동전의 개수가 4개 일 때, 사용되는 동전의 종류와 같은 해답을 찾는 과정입니다. 따라서 4번 과정을 위해서 3번 과정에서 발생한 정보들을 이용하게 됩니다. 3번 과정에서는 작은 문제에서 답이 나올 때마다 memoization처럼 배열 같은 곳에 저장합니다.