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

1. 동적 계획법

주어진 문제를 더 작은 문제로 나누고, 작아진 문제들을 해결함으로써 원래 문제를 해결해나가는 방식이다.

보통 배열을 만들어 값을 저장하고, 그것들을 통해 답을 구하는 편이다.

ex_1) 동적 계획법 예시(피보나치)

피보나치 수열을 통해 동적 계획법 구현을 이해해볼 수 있다.

+) divide and conquer

#include <iostream>
using namespace std;

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);
}

fibo(5)을 구한다고 볼 때, fibo(4), fibo(3)만을 거치는 것이 아니다.

fibo(5), fibo(4)에서 또 fibo(3), fibo(2)가 나뉘고 그 아래에서 또 두 갈래로 나뉘며 너무 많은 과정(이미 return 했던, fibo(3)을 몇 번 더 거쳐가면서 return하는 등)을 거치게 된다.

즉, 해당 경우에 재귀의 구현 방식으로는 비효율적일 수 있다.

이 때, 이전에 계산한 값을 메모리에 저장하며 동일한 계산을 반복 수행하도록 하여 실행속도를 빠르게 하는 것이 필요할 것이다.

그 과정은 아래 코드와 같이 배열에 저장하면서 해결해볼 수 있다.

2) DP_bottom-up : 작은 문제부터 올라가며 반복문으로 구현할 수 있다.

#include <iostream>
using namespace std;

vector<int> vec(10001);

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

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

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

}

ex_2) 백준 11726번

D[N]의 값은 (D[N-1]에서 세로로 긴 타일 1개 놓는 경우) + (D[N-2]에서 가로로 긴 타일 2개 놓는 경우)

+) (D[N-2]에서 세로로 2개는 D[N-1]의 경우에 포함됨)

한 D[5]까지 표를 직접 작성해보면 아래 점화식을 세울 수 있다.

D[N]=D[N-1]+D[N-2]

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

using namespace std;

vector<long> d(1001);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;

    d[1] = 1;
    d[2] = 2;

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


    return 0;
}

+) 계속 더하다 보면, 범위 초과가 발생하기 때문에 %10007을 적절한 위치에 둘 필요가 있다.