[ 알고리즘 ] 동적 계획법 ( Dynamic Programming, DP )의 이해와 구현 with C++

동적 계획법( Dynamic Programming)이란?

동적 계획법은 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다.

동적 계획법은 구체적인 알고리즘이 아닌 하나의 문제 해결 패러다임으로 볼 수 있다.

 

동적 계획법은 영문으로 표기하면 Dynamic Programming인데 이름과 달리 다이내믹하진 않고 동적 계획법의 고안자가 멋있어 보여서 이름을 이렇게 지었다고 한다. 이광근 교수는 동적 계획법을 "기억하며 풀기"라고 번역하였다.

 

동적 계획법을 사용하는 이유

동적 계획법은 일반적인 재귀와 유사하다. 하지만 재귀는 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산을 한다는 점이 동적 계획법과의 큰 차이이다.

 

이 예로 피보나치수열을 들 수가 있다.

아래 코드는 피보나치수열을 재귀로 짠 코드이다.

int fibonacci(int num)
{
	if(num <= 2)
    	return 1;
    else fibonacci(num-1) + fibonacci(num-2);
}

 

출처 : https://velog.io/@chelsea/1-%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming-DP

위 그림은 fibonacci(6)을 실행시켰을 때의 모습이다.

보다시피 계산이 중복되는 부분이 더러 보인다.

 

이러한 중복을 줄이는 기법이 동적 계획법이다.

동적 계획법의 원리는 간단하다. 한번 구한 작은 값을 저장하고 또 같은 계산을 한다면 저장한 값을 사용하는 일종의 재활용이다.

 

int DP[101] = {0,};

int fibo(int num)
{
	if(num <= 2) return 1;
 	if (DP[num]==0)
    	DP[num] = fibo(num-1) + fibo(num-2);
  	return DP[num];
}

위 코드는 피보나치 수열을 동적 계획법으로 짠 코드이다. 이렇게 짜면 중복되는 연산을 하지 않는다.

 

DP 알고리즘이 적용되려면 두 가지 조건을 만족해야한다.

1) Overlapping Subproblems(겹치는 부분 문제)
2) Optimal Substructure(최적 부분 구조)

 

1) Overlapping Subproblems

DP는 기본적으로 문제를 나누고 그 문제의 결과 값을 재활용해서 전체 답을 구한다. 그래서 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다.

위에서 예로 든 피보나치 수열이 겹치는 부분 문제의 대표 예이다.

fibo(n) = fibo(n-1) + fibo(n-2)

에서 동일한 부분문제가 중복되어 나타난다.

 

2) Optimal Substructure(최적 부분 구조)

부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우를 말한다.

즉 A-B까지의 최단 경로를 찾으려 할 때 A-X/X-B가 많은 경로 중 가장 짧은 경로라면 전체 최단 경로도 A-X-B가 된다.

 

이와 같이, 부분 문제에서 구한 최적 결과가 전체 문제에서도 동일하게 적용되어 결과가 변하지 않을 때 DP를 사용할 수 있게 된다.
피보나치 수열도 동일하게 이전의 계산 값을 그대로 사용하여 전체 답을 구할 수 있어 최적 부분 구조를 갖고 있다.

 

DP 사용하기

동적 계획법은 특정 경우에만 사용할 수 있는 알고리즘이 아닌 설계기법이기 때문에 다양한 곳에서 사용할 수 있다.

 

일반적으로 DP를 사용하기 전에는 아래의 과정을 거쳐 진행할 수 있다.

1) DP로 풀 수 있는 문제인지 확인한다.
2) 문제의 변수 파악
3) 변수 간 관계식 만들기(점화식)
4) 메모하기(memoization)
5) 기저 상태 파악하기
6) 구현하기

 

① DP로 풀 수 있는 문제인지 확인하기

이 부분부터 어렵다. 동적 계획법은 퍼포먼스가 좋은만큼 난해하고 복잡하다. 또한 다른 알고리즘보다 풀이가 직관적으로 떠오르지 않는다. 우선 현재 문제가 작은 문제들로 이루어진 하나의 함수로 표현될 수 있는지를 판단해야 한다.

 

② 문제의 변수 파악

DP는 현재 변수에 따라 그 결과 값을 찾고 그것을 전달하여 재사용하는 것을 거친다.  즉, 문제 내 변수의 개수를 알아내야 한다는 것. 이것을 영어로 "state"를 결정한다고 한다.

예를 들어, 피보나치 수열에서는 n번째 숫자를 구하는 것이므로 n이 변수가 된다. 그 변수가 얼마이냐에 따라 결과값이 다르지만 그 결과를 재사용하고 있다.

 

③ 변수 간 관계식 만들기

변수들에 의해 결과 값이 달라지지만 동일한 변수값인 경우 결과는 동일하다. 또한 우리는 그 결과값을 그대로 이용할 것이므로 그 관계식을 만들어낼 수 있어야 한다.

그러한 식을 점화식이라고 부르며 그를 통해 우리면 짧은 코드 내에서 반복/재귀를 통해 문제가 자동으로 해결되도록 구축할 수 있게 된다. ( 아쉽게도 점화식은 고교 과정에서 빠졌다. )

예를 들어 피보나치 수열에서는 f(n) = f(n-1) + f(n-2) 였다. 이는 변수의 개수, 문제의 상황마다 모두 다를 수 있다.

 

④ 메모하기

변수 간 관계식까지 정상적으로 생성되었다면 변수의 값에 따른 결과를 저장해야 한다. 이것을 메모한다고 하여 Memoization이라고 부른다.

변수 값에 따른 결과를 저장할 배열 등을 미리 만들고 그 결과를 나올 때마다 배열 내에 저장하고 그 저장된 값을 재사용하는 방식으로 문제를 해결해 나간다.

이 결과 값을 저장할 때는 보통 배열을 쓰며 변수의 개수에 따라 배열의 차원이 1~3차원 등 다양할 수 있다.

 

⑤ 기저 상태 파악하기

여기까지 진행했으면, 가장 작은 문제의 상태를 알아야 한다. 보통 몇 가지 예시를 직접 손으로 테스트하여 구성하는 경우가 많다. 

피보나치 수열을 예시로 들면, f(0) = 0, f(1) = 1과 같은 방식이다. 이후 두 가지 숫자를 더해가며 값을 구하지만 가장 작은 문제는 저 2개로 볼 수 있다.

해당 기저 문제에 대해 파악 후 미리 배열 등에 저장해두면 된다. 이 경우, 피보나치 수열은 매우 간단했지만 문제에 따라 좀 복잡할 수 있다.

 

⑥ 구현하기

개념과 DP를 사용하는 조건, DP 문제를 해결하는 과정도 익혔으니 실제로 어떻게 사용할 수 있는지를 알아보고자 한다. DP는 2가지 방식으로 구현할 수 있다.

1) Bottom-Up (Tabulation 방식) - 빠르고 효율적, 유연하지 못함
2) Top-Down (Memoization 방식) - 변화에 유연 , 모듈화를 할 수 없는 구조

 

-1 Bottom-Up

1. 문제를 크기가 작은 문제부터 차례대로 쓴다.
2. 문제의 크기를 조금씩 크게 만들면서 문제를 푼다.
3. 작은 문제를 풀면서 큰 문제의 답을 구한다.

이름에서 보이듯이, 아래에서부터 계산을 수행 하고 누적시켜서 전체 큰 문제를 해결하는 방식이다.

메모를 위해서 dp라는 배열을 만들었고 이것이 1차원이라 가정했을 때, dp[0]가 기저 상태이고 dp[n]을 목표 상태라고 하자. Bottom-up은 dp[0]부터 시작하여 반복문을 통해 점화식으로 결과를 내서 dp[n]까지 그 값을 전이시켜 재활용하는 방식이다.

(Tabulation인 이유는 table을 filling하며 table에 접근하기 때문에 이런 이름이 붙었다고 하며 memoization과 유사하다. )

int fibo(int n)
{
  DP[0] = 0;
  DP[1] = 1;
  for (int i=2; i<=n; i++)
    DP[i] = DP[i - 1] + DP[i - 2];
  return DP[n];
}

-2 Top-Down

1. 큰 문제를 작은 문제로 나눈다.
2. 작은 문제를 푼다.

이는 dp[0]의 기저 상태에서 출발하는 대신 dp[n]의 값을 찾기 위해 위에서 부터 바로 호출을 시작하여 dp[0]의 상태까지 내려간 다음 해당 결과 값을 재귀를 통해 전이시켜 재활용하는 방식이다.

int DP[101] = {0,};

int fibo(int num)
{
	if(num <= 2) return 1;
 	if (DP[num]==0)
    	DP[num] = fibo(num-1) + fibo(num-2);
  	return DP[num];
}

 

DP의 장단점

동적 계획법은 모든 방법을 검토해 보고 결과적으로 효율적인 값을 택한다.

이 때문에 동적 계획법은 시간이 오래 거릴지만 항상 최적의 값을 구한다.

 

DP 구현

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

1003번: 피보나치 함수

위에서 예로 든 피보나치 함수와 관련된 DP문제다.

해당 문제를 위에서 설명한 DP의 사용과정을 통해 풀어보도록 하자.

 

1) 해당 문제가 DP로 풀 수 있는지 확인하기 

피보나치 수열에서 fibo(0)과 fibo(1)이 몇번 실행됐는지 구하는 문제이다. 이를 재귀로 풀었을 시 매번 재귀함수를 0까지 돌려야 해서 시간 초과가 난다. 때문에 이 문제는 DP로 풀 수 있다.

 

2) 문제의 변수 파악

n번째 피보나치 수에서 fibo(0)과 fibo(1)이 몇번 실행됐는지 구하는 문제이기에 때문에 변수는 n이다.

 

3) 변수 간의 관계식 만들기

n	zero	one
0	1	0
1	0	1
2	1	1
3	1	2
4	2	3
5	3	5
6	5	8

0의 출력횟수는 DP[n-1], 1의 출력횟수는 DP[n]

 

4) 메모하기

간단히 피보나치 수열을 메모하면 된다.

DP[n] = DP[n-1] + DP[n-2]

 

5) 기저 상태 파악하기 

DP[0] = 0

DP[1] = 1

 

6) 구현하기 - Bottom_up

#include <iostream>

using namespace std;

int fibo_data[41] = {0,1,1};
int T,n;

int main(void)
{
	ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    for(int i = 3; i <= 40; i++) fibo_data[i] = fibo_data[i-1] + fibo_data[i-2];
    
    cin >> T;
    
    while(T--)
    {
		cin >> n;
        if(n == 0) cout << "1 0\n";
        else cout << fibo_data[n-1] << " " << fibo_data[n] << "\n";
	}
    
    return 0;
}