[C++ 알고리즘] 동적 계획법(Dynamic Programming)

개념

동적계획법의 정의는 아래와 같다.

처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산하는 방식.

정의만 가지고는 이해하기 쉽지 않다. 뒤에서 설명하겠지만, 결론적으로 말하자면 배열을 만들어 값들을 저장하고, 후에 그것들을 가지고 답을 구하는 방법이다.

 

동적 계획법을 이용해 문제를 풀려고 한다면 먼저 점화식을 세워야 한다. 점화식이라는 것은 어떤 수열의 일반항을 이전의 항들을 이용해 정의한 식이다. 고등학교 때 배웠던 수열의 일반항을 구하듯이 n번째 항을 구하는 방법을 식으로 나타낸다고 생각하면 쉽다. 예를 들어 흔히들 아는 피보나치 수열의 점화식은 아래와 같다.

 

이제 이 식을 가지고 코드로 작성을 해 보도록 하자. 일반적으로 재귀함수를 이용해 작성을 하는데 그렇게 하면 아래와 같은 코드가 나올 것이다.

#include <iostream>
using namespace std;

//피보나치 수열을 계산하는 함수 by 재귀
int fibo(int x) {
	if (x <= 1) return x;
	return fibo(x - 1) + fibo(x - 2);
}


int main() {
	int T;
	cin >> T;
	cout << fibo(T);
}

그런데 이렇게 실행을 한다면 컴퓨터가 같은 일을 굉장히 많이 반복하게 된다. 만일 피보나치 수열의 6번째 항을 구한다고 가정하자. 그렇다면 컴퓨터는 아래 작업들을 수행하게 된다.

그림을 보면 fibo(2)를 구하는 과정이 3번 반복된다. 이것 말고도 그림을 자세히 보면 같은 작업을 컴퓨터가 계속 반복하게 된다는 것을 알 수 있다. fibo(3)을 구하는 과정도 2번이나 반복된다. 수가 커지면 커질수록 이러한 중복되는 과정은 기하급수적으로 증가하게 될 것이다. 이때 사용하는것이 메모이제이션(memoization) 기법이다. 메모이제이션의 정의는 아래와 같다.

컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 

 

앞서 "배열을 만들어 값들을 저장한다." 라고 했는데 이것이 메모이제이션 기법의 예시이다. fibo(2) = fibo(1)+fibo(0)=2 라는 것을 한번 구했다면 이것을 배열의 2번째 인덱스에 저장하고(첫번째에 저장해도 되지만 직관적으로 사용하기 위해 0번 인덱스는 주로 비워둔다.) 나중에 또 fibo(2)의 값이 필요해지면 두번째 인덱스에 있는 값을 꺼내와서 사용하는 것이다. 그러니 앞서 작성한 재귀용법에 방금 배운 동적 계획법을 적용하려면 두가지를 추가하면 된다.

• 만약 배열의 해당 인덱스가 0이 아니라면(비어있지 않다면) 그 값을 리턴한다
• 값을 배열에 저장한 뒤 그 값을 리턴한다.

핵심은 여태까지는 값을 리턴하기만 했지만 이제는 배열에 값을 저장한다는 것이다. 아래 코드를 보면 배열에 값을 저장하는 부분이 추가되어 있다.

#include <iostream>
using namespace std;

//피보나치 수열의 값을 저장할 배열
int arr[10001];

//피보나치 수열을 계산하는 함수 by 동적계획법
int fibo(int x) {
	//초기 조건, fibo(0)=0 fibo(1)=1
	if (x <= 1) {
		arr[x] = x;
		return arr[x];
	}
	//만약 이미 값을 구한 경우라면 앞서 구한 값을 사용한다.
	if (arr[x] != 0) {
		return arr[x];
	}
	arr[x] = fibo(x - 1) + fibo(x - 2);
	return arr[x];
}


int main() {
	int T;
	cin >> T;
	cout << fibo(T);
}

위 코드를 보면 알 수 있듯이 이미 값을 구했다면 재귀함수를 다시 호출하는것이 아니라 구한 값을 사용한다는 것이다. 즉 같은 값을 다시 계산할 필요가 없다.

 

시간복잡도

시간복잡도는 어렵지 않게 구할 수 있다. 

배열의 크기(혹은 테이블의 크기) X 한 칸을 채울때 걸리는 시간

최악의 경우 모든 배열을 채워야 하기 때문에 식이 위와같이 나온다. 만일 피보나치 수열을 동적 계획법으로 구현했을 경우에, 최악의 경우 n번째 항까지 배열을 채워야 하기 때문에 배열의 크기는 n, 한칸을 채우는 데에 걸리는 시간은 일정한 시간. 즉 1이기 때문에 위 코드의 시간복잡도는 O(n)이다.

 

Top-down vs Bottom-up

동적 계획법을 구현하는 방법에는 크게 두가지가 있는데 위에서 구현한 대로 재귀를 이용해 구하는 방식이 Top-down방식이다. 위 방법에서 int x, 즉 함수 인자 부분에 들어오는 수가 점점 작아진다(5->4->3 ...) 이제 Bottom-up방식에 대해 알아보자. 두가지의 차이점은 아래와 같다.

Top-down	Bottom-up
큰 문제를 쪼개나간다.	작은 문제부터 올라간다.
재귀로 구현한다.	반복문으로 구현한다.

그럼 반복문을 이용해서 앞서 만든 피보나치 함수를 다시 만들어 보자.

#include <iostream>
using namespace std;

int arr[10001];

int main() {
	int T;
	cin >> T;

	//초기값 세팅
	arr[0] = 0;
	arr[1] = 1;

	for (int i = 2; i <= T; i++) {
		arr[i] = arr[i - 1] + arr[i - 2];
	}
	cout << arr[T];

}

위 코드를 보면 i의 값이 2부터 T까지 증가하는 것을 볼 수 있다. 위와 같이 작은 문제부터 구하는 것을 Bottom-up방식이라고 한다.

 

같이 풀면 좋은 문제

아래 문제들은 내가 dp를 배우고 풀었던 문제들이다. 

 

 

위에서 다뤘던 피보나치 수열을 조금 응용한 문제이다.

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

1003번: 피보나치 함수

 

---

dp를 이용해서 풀 수 있는 문제이다. 점화식을 어떻게 세울지 생각하며 풀어보자.

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

1463번: 1로 만들기

<풀이>

https://sectumsempra.tistory.com/84

[백준 1463] -1로만들기(C++)/다이나믹 프로그래밍

 

---

어떻게 계단을 올라가야 최고점수를 얻을 수 있는지 생각하며 문제를 풀도록 하자. 연속된 3개의 계단을 밟지 않기 위해서는 어떻게 해야 할지 생각해보자. 어렵다면 아래 힌트를 보고 다시 도전해보자. (힌트는 아래 흐린 글씨로 적혀있다.)

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

2579번: 계단 오르기

 

 

 

 

 

 

 

힌트 : n번째 계단까지 오르는 경우는 n-3까지 오르고 2칸 1칸을 오르거나, n-2까지 오르고 2칸을 오르는 경우가 있다. 둘 중 어떤 값이 최댓값일가? (만일 n-1까지 오르고 한칸을 더 올라간다고 할 경우, 연속해서 세 계단을 밟는 경우가 발생할 수 있다.)

---

2xn타일링은 1, 2가 각각 있는데 만일 푸는 방법을 몰랐다면 1을 푸는 방법을 이해하고, 2를 혼자 풀어보도록 하자. 아이디어만 떠올린다면 구현하는것은 크게 어렵지 않다.

 

2xn타일링

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

11726번: 2×n 타일링

2xn타일링 2

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

11727번: 2×n 타일링 2

---

이 문제는 특이하게 bottom-up을 적용한다.

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

17626번: Four Squares

---

이 외에도 아래 링크(백준-다이나믹 프로그래밍)에 들어가면 dp를 이용해 푸는 많은 문제들을 볼 수 있다.

https://www.acmicpc.net/problemset?sort=ac_desc&algo=25 

문제 - 1 페이지