[알고리즘 정리] - 동적 계획법(Dynamic Programming)

 

 

목차
1. 들어가며
2. 동적계획법이란
3. 예제 적용

 

 

 

들어가며

 코딩테스트 단골 문제로 등장하는 동적 계획법, 일명 DP에 대해 정리해보려고한다. 정말 자주 출제되는 유형임에도 문제 유형이 DP인지 파악하기가 정말 어렵다. 그리고 그만큼 어려운게 사실이니 이번에 알아보자.

 

 

 

동적계획법이란

동적계획법 (Dynamic Programming)

 

 

 

 

 

 먼저 동적 계획법이란 복잡한 문제를 여러개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법을 뜻한다.

 

 

 

 

 

 

 

 

 

 즉, 작은 문제들을 해결하여 큰 문제를 해결하는 방식의 기법인데, 동적 계획법이라는 이름과 전혀 매칭이 되지 않는다. 위키백과에는 이 이름의 유래에 대해 아래와 같이 설명한다. 알고리즘과 그 이름이 매칭이 안되서 찾아본 결과 이런 유래가 있었다고 한다. 

 

 

 

즉, 'Dynamic'이라는 말은 벨만이 이런 알고리즘의 '시가변적이며 다단계적인' 특성을 나타내기 위해서 채택한 용어인 것이다. 또한 'Programming'이라는 단어는 공군 내에서도 워드 프로세스 교육이나 군수 물자 운송 등에 이용되는 단어였기 때문에 사용하는데 아무 제약이 없었던 것이다. 이렇게 만들어진 '동적 계획법'이라는 단어는 선형 계획법이나 수리 계획법처럼 하나의 프로그래밍 기법을 나타내는 단어가 되었다. - 위키백과

 

 

 

 

 

 

 

 

 

 

 

 

동적계획법의 원리와 구현 방식

 

1. 큰 문제를 작은 문제로 나눌 수 있어야 한다.

2. 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 한다.

3. 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용 시 이 DP테이블을 이용한다. 이를Memoization 기법 이라고 한다.

4. 동적계획법은 톱-다운 방식과 바텀-업 방식으로 구현할 수 있다.

 

 

 

 

 

 

 

 동적계획법에서 가장 중요한 것은 그 문제가 동적계획법으로 풀수 있는가 이다. 위에서 나와있듯이 동적계획법문제는 작은 문제들이 반복돼서 나오고 이를 '한 번'만 계산해서 연산 시간을 최적화하는 기법이다. 

 

 

 

 

 

 

 

 문제가 동적계획법으로 풀 수 있다는 것을 알았다면 문제를 풀기위한 점화식을 세워야한다. 가장 대표적으로 n번째 피보나치 수를 구하기 위한 점화식은 'Fibo[n] = Fibo[n - 1] + Fibo[n - 2]'이다. 이는 피보나치 수열의 공식 자체가 동적계획법의 점화식이기 때문이다.

 

 

 

 

 

예제 적용

 

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

11726번: 2×n 타일링

 

 

 

 

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

// memo[i] -> 2xi 크기의 타일을 채우는 방법의 수

// 블록을 오른쪽으로 채워나간다고 하였을 때, 블록을 마무리하는 방법은 두가지 존재한다.
// 블록을 세로로 하나 놓거나 가로로 2개를 놓는 것이다.

// 블록을 채워넣는 방법의 수는 계산할때마다 달라지는 것이 아니므로 dp로 풀 수 있으며,
// 이전에 채웠던 방법의 수를 이용해 이후의 방법의 수도 구할 수 있다.


// 점화식 : memo[i] = memo[i - 1] + memo[i - 2]; 


long long memo[1001]{ 0, };
int n;
void input() {
	cin >> n;

	return;
}


int main() {
	input();

	memo[0] = 0;
	memo[1] = 1;
	memo[2] = 2;
	
	for (int i = 3; i <= n; i++) {
		memo[i] = (memo[i - 1] + memo[i - 2]) % 10007;
	}

	cout << memo[n];

	return 0;
}

 

 

 

 

 

 

 

 동적계획법에서 중요한것은 이 문제가 동적계획법으로 풀 수 있는가를 판단하는 능력이라고 생각한다. 이 문제에서는 2xi 크기의 블록을 오른쪽으로 채워나간다고 했을 때, 마무리하는 방법이 2가지임에 착안하여 생각해봐야 했다. 세로로 하나의 블록을 놓거나 2개의 블록을 가로로 놓거나 오로지 2가지 방법만이 존재하며 그 이전의 블록들을 놓는 방법의 수는 고정되어 있다. 즉, 이전의 작은 문제의 답이 고정되어 있고 새로운 문제를 해결하기 위해 이전의 값들을 계속해서 사용할 수 있으므로 동적계획법을 통해 해결할 수 있었다.

 

 

 

 

 

 문제가 동적계획법으로 풀 수 있는지를 판단할 수 있는 근거는 아래와 같다고 생각한다.

 

1. 이전의 값들을 계속 사용해야 하는가?
2. 이전에 계산한 값들이 달라지지 않고 일정한가?

 

 

 

 

 

 

 

 

 

 난이도가 있는 DP 문제의 경우 그리디 알고리즘과 결합하여 max혹은 min함수를 사용하여 최선의 값을 DP에 기록해야하는 경우도 많았다. 또한 통제되어야하는 변수에 따라 DP배열을 2차, 3차로 놓아야 하는 경우도 있었다. 이러한 문제들에 관해서는 계속해서 예제를 통해 훈련을 해나가야 할 것 같다.