다이나믹 프로그래밍(Dynamic Programming)

1. 의미

다이나믹 프로그래밍이란, 동적계획법이라고도 불리는데 위키백과에 따르면 다음과 같다.

 

수학과 컴퓨터 공학, 그리고 경제학에서 동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.

 

복잡한 문제를 간단한 여러 개의 문제로 나누어 푼다는 것이 핵심이다!

 

요약하면 큰 문제 -> 작은 문제로 나눠서 푸는 알고리즘이다.
그런데, 분할정복도 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다. 
단, 분할 정복은 작은 문제들이 중복이 되진 않지만, 다이나믹 프로그래밍은 중복된 작은문제를 푸는 것이라는 차이점이 존재한다.

2. 속성 

다이나믹 프로그래밍으로 문제를 해결하기 위해서는 두 가지 속성이 필요하다.
1) Overlapping Subproblem 부분 문제들이 겹친다
ex) 피보나치 F(n) = F(n-1) + F(n-2)

2) Optimal Substructure 최적 부분 구조
ex) 서울에서 부산을 가는 가장 빠른 길이 대전과 대구를 거쳐야 한다면
대전에서 부산을 가는 가장 빠른 길은 대구를 거쳐야 한다.

각 문제는 한번만 풀어야 한다.
Optimal substructure를 만족하기에, 같은 문제는 구할 때마다 정답이 같다.
정답을 한 번 구했으면, 어딘가에 메모해야 한다(ex. 배열).
메모를 한다고 해서 영어로는 Memoization 이라고 한다.

재귀함수로 피보나치를 구하면 시간복잡도 O(2^n)
DP로 피보나치를 구하면 시간복잡도 O(n)

3. 활용

DP에는 두 가지 해결법이 있다.
1) Top-down 
2) Bottom-up
때로는, Top-down이 빠를 수도 있다(그러나 대부분은 확실하지 않고 비슷하다)

문제 풀이 전략에 대해서, DP 문제를 어떻게 풀 것인가?
1) 점화식을 세운다(ex. F(n) = F(n-1) + F(n-2))
N 번째 정답이라고 했을 경우, D[N] 배열을 통해 정답 구하기

2) 문제를 작은 것으로 나눈 후 문제 해결하기

 

 

4. 문제 풀이

1. 1로 만들기

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

1463번: 1로 만들기

풀이

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int go(int x);
vector<int> arr;


int main() {
	
	int n;
	cin >> n;
	arr.assign(n+1, 0);

	// 함수 호출
	cout << go(n);
	
	return 0;
}
int go(int x) {
	// 1 일경우 그냥 탈출
	if (x <= 1)
		return 0;
	
	// 값이 이미 정해졌을 경우
	if (arr[x] > 0)
		return arr[x];

	// 1까지 내려가기
	arr[x] = go(x - 1) + 1;

	// 2로 나눌 수 있다면
	if (x % 2 == 0) {
		int val = arr[x / 2];
		// 더 작은 값이 있으면 갱신
		if (arr[x] > arr[x / 2]) arr[x] = arr[x / 2] + 1;
	}

	// 3으로 나눌 수 있다면
	if (x % 3 == 0) {
		int val = arr[x / 3];
		// 더 작은 값이 있으면 갱신
		if (arr[x] > arr[x / 3]) arr[x] = arr[x / 3] + 1;
	}

	return arr[x];
}

2. 2xn 타일링

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

11726번: 2×n 타일링

풀이

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;


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

	vector<int> d;
	d.assign(n + 1, 0);
	
	d[0] = 1, d[1] = 1;

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

	cout << d[n];

	return 0;
}

3. 1, 2, 3 더하기

문제 : https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

풀이

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> d;

int main() {
	int n,m;
	cin >> m;
	
	// 반복처리
	for (int cnt = 0; cnt < m; cnt++) {
		cin >> n;
		d.assign(n + 1, 0);
		d[1] = 1, d[2] = 2, d[3] = 4;
		for (int i = 4; i <= n; i++) {
			d[i] = d[i - 1] + d[i - 2] + d[i - 3];
		}
		cout << d[n] << endl;
	}
}

4. 카드 구매하기

문제 : https://www.acmicpc.net/problem/11052

11052번: 카드 구매하기

풀이

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int max(int, int);
int main() {
	int n;
	cin >> n;

	// 입력
	vector<int> d;
	vector<int> a;
	d.assign(n + 1, 0);
	a.assign(n + 1, 0);

	for (int i = 1; i <= n; i++)
		cin >> a[i];
	
	// 처리
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			d[i] = max(d[i], a[j] + d[i - j]);
		}
	}
	cout << d[n];
}

int max(int a, int b) {
	if(a>=b)
		return a;
	else
		return b;
}