동적 계획법 (1)

 
 

동적 계획법이란?

1. 메모이제이션
2. 타뷸레이션
3. 부분집합의 합 문제
4. 문자열과 시퀀스에 대한 동적 계획법

해당 게시물은 다음 작업을 수행할 수 있는 지식을 담았다.
 

• 주어진 문제에 동적 계획법을 적용할 수 있는지 분석하는 능력
• 메모이제이션과 타뷸레이션 기법을 서로 비교하여 적절한 방법을 선택함
• 메모이제이션을 위한 적절한 캐시 사용 방법을 찾을 수 있음
• 직관적인 전수 조사 방법을 사용하여 주어진 문제를 분석
• 점진적으로 최적화 알고리즘을 구현하면서 동적 계획법 해법을 개발할 수 있는 능력

 
해당 게시글에서는 동적 계획법에 대해 소개하겠다.
그리고 컴퓨터 과학 분야에서 널리 알려진
몇몇 문제를 동적 계획법으로 해결하는 방법에 대해 알아보겠다.
 
많은 프로그래머가 좋아하기도하고 동시에 두려워하기도 하는 동적 계획법은
분할 정복 패러다임 개념을 확장한 것으로, 특정 분류의 문제에 사용된다.
동적 계획법 문제들은 매우 복합적이며 창의력과 인냄심, 추상적 개념을 시각화하는 능력 등을
요구하는 경우가 많아서 어렵게 느껴지곤 한다.
그러나 이러한 문제들의 다수 근사하고 놀라울 정도로
간단한 해결 방법을 가지고 있으며,
프로그래머에게 직관적인 작업 방식을 크게 뛰어넘는 통찰력을 선사하기도 한다.
 
분할 정복과 그리디 알고리즘 같은 기법은 특정 상황에서는 상당히 효과적이지만,
그렇지 않은 경우에는 최적화의 결과를 도출하지 못할 수 있다.
예를 들어 음수 에지 가중치를 가진 그래프에서 벨만-포드 알고리즘은
최적의 해를 찾을 수 있지만 다익스트라 알고리즘은 그렇지 않다는 점이 있다.
앞서 언급한 기법으로 해결할 수 없는 문제 중에서
재귀적으로 표현할 수 있는 문제는 아마도 동적 계획법이 가장 적합할 수 있다.
 
동적 계혹법 문제는 매우 다양한 상황에서 만날 수 있다.
다음은 동적 계획법이 자주 사용되는 몇 가지 예이다.
 

• 조합 (특정 기준을 만족하는 시퀀스의 조합 또는 순열의 개수 구하기)
• 문자열과 시퀀스(편집 거리(cdit distance), 최장 공통 부분 시퀀스(longest common subsequence),
• 최장 증가 부분 시퀀스(longest increasing subsequence) 등)
• 그래프 (최단 경로 문제)
• 머신 러닝 (음성/얼굴 인식)

 
그럼 동적 계획법의 기본 개념부터 알아보자.
 
 

동적 계획법이란?

 
예제를 통해 동적 계획법이 무엇인지 알아보겠다.
다음은 피보나치 수열의 일부이다.

{ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... }

 
앞에 나열된 수열을 살펴보면, 세 번째 이후의 원소 값은
바로 앞 두 개 원소의 합과 같다는 것을 알 수 있다. 이를 수식으로 표현하면 다음과 같다.
 

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

 
이 수식으로부터 피보나치 수열이 재귀적인 관계를 가지고 있음을 알 수 있다.
원소 F(n)은 이전 원소 F(n-1)과 F(n-2) 값에 의해 결정되며,
앞에 나타난 F(n) = F(n-1) + F(n-2) 수식은 이 수열의 재귀관계(recurrence relation)를 표현한다.
이 수열의 처음 두 원소 F(0)과 F(1)은 기저 조건(base case)이라고 부르며,
이는 더 이상 재귀가 없어도 해를 구할 수 있는 지점을 나타낸다.
이러한 과정을 그림으로 표현하면 다음과 같다.
 

위 그림은 다음과 같이 문장 형태로도 기술할 수 있다.
 

 
이와 같이 계속 재귀적으로 기술되는데
이와 같은 방식을 하향식 해법이라고 부른다.
왜냐하면 전체 해결 방법을 트리 형태로 구성한 재귀 트리의 맨 꼭대기에서 시작하여
기저 조건에 닿을 때까지 아래쪽 가지(branch)로 이동하기 때문이다.
이러한 연산을 C++ 재귀 함수로 구현하면 다음과 같다.
 

int Fibonacci(int n)
{
	if (n < 2)
		return n;

	return Fibonacci(n - 1) + Fibonacci(n - 2);
}

 
 
트리를 자세히 관찰하면 최종 해답을 찾기 위해 여러 개의 부분 문제(subproblem) 또는
중간 단계 문제를 풀어야 한다는 점을 알 수 있고,
또한 이러한 부분 문제는 한 번 이상 나타난다는 점을 발견할 수 있다.
예를 들어 F(2)는 F(4)와 F(3)을 구하는 과정에서 중복해서 나타난다.
왜냐하면 F(4) = F(3) + F(2) 이고, F(3) = F(2) + F(1)이기 때문이다.
그러므로 피보나치 수열은
중복되는 부분 문제(overlapping subproblem)라는 특성을 가지고 있다고 말할 수 있다.
이는 일반적인 분할 정복 문제와 동적 계획법 문제를 구분하는 특성 중 하나이다.
분할 정복 문제에는 전체 문제가 독립적인 부분 문제로 나뉘는 경향이 있지만,
동적 계획법의 경우에는 같은 부분 문제가 반복적으로 나타난다.
 
또한 여러 부분 문제가 서로 완전히 동일하다는 것을 알 수 있다.
예를 들어 F(2)의 해를 구해야 할 경우,
이것이 F(4) 또는 F(3) 중에서 어느 것을 구하기 위해 필요한지에 상관없이 같은 방식의 연산을 수행하면 된다.
이를 최적 부분 구조(optimal substructure)라고 부르며,
이것이 동적 계획법 문제를 정의하는 두 번째 특성이다.
전체 문제에 대한 최적해가 부분 문제의 최적해의 조합으로 표현할 수 있을 때
최적 부분 구조를 갖는다고 표현한다.
 
어떤 문제를 동적 계획법으로 해결하려면 두 가지 속성을 만족해야 한다.
중복되는 부분 문제 특성으로 인해 문제의 복잡도가 입력이 증가함에 따라
기하급수적으로 증가하는 경향이 있지만,
최적 부분 구조 속성을 활용하면 복잡도를 크게 줄일 수 있다.
동적 계획법에서 본질적으로 반복 계산을 피하기 위해 이전에 해결한 부분 문제의 해답을
캐시에 저장하는 방식을 사용한다.
 
 

메모이제이션 : 하향식 접근 방법

 
이번 주제에서 살펴볼 기법은 메모를 한다는 의미인 '메모이제이션(memoization)'이다.
암기를 뜼하는 '메모리제이션(memorization)'과 혼동하지 않기 바란다.
메모이제이션을 사용하여 최적 부분 구조 특성을 갖는 피보나치 수열에 대해 하향식 해법을 재구성할 수 있다.
프로그램 로직은 이전과 같지만,
각 단계에서 부분 문제의 해답을 찾으면 이를 배열 구조의 캐시에 저장한다.
배열의 인덱스는 현재의 n값을 사용할 것이며,
여기서 n은 피보나치 수열 문제 풀이 단계의 매개변수 집합 또는 상태 (state)를 나타낸다.
함수 F(n)이 호출될  때마다 먼저 F(n)의 상태가 이미 캐시에 저장되어 있는지를 확인한다.
만약 캐시에 값이 저장되어 있다면 단순히 이 값을 반환한다.

const int UNKNOWN = -1;
const int MAX_SIZE = 100;

vector<int> memo(MAX_SIZE, UNKNOWN);

int Fibonacci(int n)
{
	if (n < 2)
		return n;

	if (memo[n] != UNKNOWN)
		return memo[n];

	int result = Fibonacci(n - 1) + Fibonacci(n - 2);
	memo[n] = result;
	return result;
}

 
위에 기술한 함수를 이용하여 Fibonacci(5)를 구하는 재귀 트리 구조는 아래와 같이 나타낼 수 있다.
 

캐시를 사용하여 피보나치 수열에서 N번째 원소 계산하기 (N = 5) 마지막 노란색은 F(0)이다. 오탈자다.

 
이러한 방식을 통해 상당히 많은 중복 작업을 제거할 수 있다.
이처럼 하향식 방식에서 부분 문제의 해를 캐시에 넣어 사용하는 기술을 메모이제이션이라고 하며,
이 방법은 모든 동적 계획법 문제에 적용할 수 있다.
이때 다음 조건을 만족한다고 가정한다.
 

1. 고유한 특성은 유지하면서 서로 다른 상태의 유사성을
2. 활용하는 캐시 사용 방식을 고안할 수 있다.
3. 사용 가능한 스택 공간을 초과하기 전에
4. 필요한 모든 부분 문제의 해답을 누적할 수 있다.

첫 번째 항목은
부분 문제 해법을 캐시에 인덱싱하여 저장하는 방법이 유효하고 유용해야 한다는 점을 의미한다.
캐시 사용 방법이 유용하려면 같은 의미의 부분 문제 해법을 정확하게 일치시켜 저장해야 한다.
또한 캐시 사용 방법이 유용하려면 너무 특정 상태에만 치우치게 동작하면 안 된다.
예를 들어 모든 부분 문제가 같은 위치의 캐시를 참조한다면
"if (memo[KEY] != UNKNOWN)"와 같은 조건에 거릴는 경우가 거의 없을 것이다.
 
두 번째 항목은 스택 오버플로(stack overflow)가 발생할 가능성에 관한 것으로,
이는 너무 많은 제귀 함수 호출을 필요로 하는 하향식 접근 방법에서 근본적으로 발생하는 문제이다.
스택 오버플로는 정해진 호출 스택 메모리보다 많은 메모리를 사용할 때 발생한다.
주어진 문제가 재귀 호출을 너무 많이 필요할 경우,
메모이제이션을 사용하지 못할 수도 있다.
늘 그렇듯이, 어떤 방법을 사용할 것인지를 선택하기에 앞서
주어진 문제의 잠재적인 복잡도를 평가하는 작업은 유용하다.
 
동적 계획법 문제에서 메모이제이션은 상당히 괜찮은 최적화 방법이다.
그러나 많은 경우 더 나은 방법을 선택할 수 있으며,
이 방법에 대해서는 다음 챕터에서 알아보자.
 
 

타뷸레이션: 상향식 접근 방법 (핵심)

 
동적 계획접의 핵심은 메모이제이션과 반대 방식의 접근 방법인
타뷸레이션(tabulation)이라고 할 수있다.
사실 동적 계획법이라는 용어가 메모이제이션과 타뷸레이션 두 가지 모두에 적용되긴 하지만,
일반적으로는 타불레이션을 더 많이 의식하여 사용한다.
 
타뷸레이션은 기저 조건 해답부터 시작하여
모든 부분 문제에 대한 해답을 표에 저장한 후 재사용하는 방식이다.
타뷸레이션 방식은 각각의 부분 문제 상태를 재귀적으로 표현할 수 있어야 하기 때문에
메모이제이션 방법보다 개념적으로 더욱 어렵게 느껴진다.
 
타뷸레이션을 이용하여 피보나치 수열을 계산하는 함수는 다음과 같이 작성할 수 있다.
 

int Fibonacci(int n)
{
	vector<int> DP(n + 1, 0);
	DP[1] = 1;

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

	return DP[n];
}

 
피보나치 예제는 상대가 1차원으로 표한되고 n이 1보다 큰 경우에 항상
F(n) = F(n-1) + F(n-2) 수식 하나로 사용하기 때문에 매우 간단하다.
그러나 많은 동적 계획법 문제가 상태를 다차원으로 표현해야 하고,
상태 전환 방식을 여러 개의 조건식으로 표현해야 할 경우도 있다.
이러한 경우 현재 상태를 제대로 표현하려면
문제에 대한 포괄적인 이해와 상당한 창의력이 필요하다.
 
타뷸레이션 방법의 장점은 꽤 많다.
타불레이션 방식은 메모리 사용량 관점에서 매우 효율적이며,
또한 그 가능한 모든 상태를 기록하는 룩업 테이블 (lookup table)을 생성할 수 있다.
그러므로 주어진 문제에 대해 임의의 여러 상태를 참조해야 하는 경우에
타뷸레이션이 최선의 방법이 될 수 있다.
 
보통 메모이제이션으로 해결할 수 있는 모든 문제는 타뷸레이션 방식으로도 재구성할 수 있으며,
그 반대도 가능하다. 주어진 문제를 메모이제이션 방식으로 풀이해보면
이 문제를 타뷸레이션 방식으로 해결하기 위해 어떻게 접근해야 하는지에 대한 감을 얻을 수 있다.
이제부터 몇 가지 전형적인 동적 계획법 문제에 대해 알아보고,
전수 조사 방법을 포함한 다양한 접근 방법과 타뷸레이션에 의한 해결 방법까지 알아보겠다.
 

부분집합의 합 문제

 
디지털 금전등록기 로직을 구현한다고 가졍햅자.
계산원이 고객에게 잔돈을 거슬러주어야 할 때,
현재 금전등록기에 남아 있는 동전을 조합하여
필요한 거스론돈을 만들 수 있는지를 화면에 표시하려고 한다.
예를 들어 제품이 7500원이고 고객이 10000원을 지불했다면 현재 금전 등록기에서
정확하게 2500원의 거스름돈을 꺼낼 수 있는지를 표시해야 한다.
 
현재 금전등록기에 1000원 지폐 다섯 장과 500원 동전 네 개, 100원 동전 15개가 있다고 가정할 경우,
거스름돈 2500원을 만들기 위해 다음과 같은 방식을 조합할 수 있다.
 

• 1000원 지폐 2장, 500원 동전 1개
• 1000원 지폐 2장, 100원 동전 5개
• 1000원 지폐 1장, 500원 동전 3개
• 1000원 지폐 1장, 500원 동전 2개, 100원 동전 5개
• 1000원 지폐 1장, 500원 동전 1개, 100원 동전 10개
• 1000원 지폐 1장, 500원 동전 1개, 100원 동전 10개
• 1000원 지폐 1장, 100원 동전 15개
• 500원 동전 4개, 100원 동전 5개
• 500원 동전 3개, 100원 동전 10개
• 500원 동전 2개, 100원 동전 15개

위에 나열된 경우의 수를 살펴보면,
이 문제는 다소 직관적으로 모든 화폐 조합을 시도해보는 방법으로 해결할 수있다.
그러나 만약 필요한 잔돈이 73270원이고,
현재 금전등록기에 50000원권, 10000원권, 1000원권과 500원, 100원, 50원, 10원 동전들이
전체 100개가 들어 있다면 어떨까?
이러한 경우에는 가능한 모든 조합을 시도해보면서 거스름돈 금액을 맞추는 것은 너무 복잡해지고,
실제로 구현하는 것이 비현실적이라고 생각할 수 있다.
이것이 바로 부분집합의 합 문제(subset sum problem)라고 알려진 고전적인 문제이다.
부분집합의 합 문제를 한 문장으로 표현하면 다음과 같다.
 
"음수가 아닌 정수로 이루어진 집합 S와 임의의 정수 x가 주어질 때,
S의 부분집합 중에서 그 원소의 합이 x와 같은 부분집합이 존재하는가?"
 
부분집합의 합 문제의 예를 하나 살펴보겠다.
 

S = { 13, 73, 45, 29 }
x = 42 -> True (13 + 29)
x = 25 -> False

 
 
집합 S가 S = { 13, 79, 45, 29 } 형태로 주어질 경우,
S로부터 다음과 같은 16개의 부분집합을 추출할 수 있다.
 

{}
{13}
{79}
{45}
{29}
{13,79}
{13,45}
{79,45}
{45,29}
{13,79,45}
{13,79,29}
{13,45,29}
{79,45,29}
{13,79,45,29}

 
집합 S의 원소 개스와 집합 S로부터 조합 가능한 부분집합의 개수를 함꼐 나열하면 다음과 같다.
다음은 콜론(:) 왼쪽은 집합 S의 원소 개수이고, 오른쪽은 부분집합의 개수를 나타낸다.
 

0: 1
1: 2
2: 4
3: 8
4: 16
5: 32
6: 64
7: 128
...

 
위에 나열된 숫자를 살펴보면
원소 개수가 n인 집합 S의 전체 부분집합 개수는 2^n개임을 알 수 있으며,
이는 n이 증가함에 따라 부분집합 개수가 기하급수적으로 증가함을 의미한다.
만약 n이 10 이하의 숫자인 경우라면 모든 집합을 다 검사하는 방법도 그리 나쁘지 않다.
그러나 앞에서 예로 들었던 금전등록기처럼 100개의 지폐 또는 동전이 들어 있는 경우라면
전체 1267650600228229401496703205376가지의 부분집합을 검사해야한다.