[Algorithm] 5주차 스터디 - 다이나믹 프로그래밍

Dynamic Programming

다이나믹 프로그래밍(DP) 즉, 동적 계획법은 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하고 다시 큰 문제를 해결할 때 사용하는 기법이다.

DP는 재귀와 유사하지만 재귀는 사용하면 동일한 계산이 여러번 반복되어 비효율적인 계산이 될 수 있다는 점이 DP와 큰 차이점이다. DP는 재귀의 이러한 단점을 개선해준다. 

DP를 구현하는 방법 중 가장 많이 사용하는 방법은 `Memoization(메모이제이션)`이다. Memoization은 한번 구한 결과를 메모리 공간에 메모해두고 같은 식을 호출하면 메모한 결과를 그대로 가져오는 기법이다. 값을 기록한다는 점에서 `Cashing(캐싱)`이라고도 한다.

DP는 주어진 문제가 DP유형인지 파악하는 것이 중요하다. 따라서 DP를 사용할 때 반복된 계산이 있는지 그리고 메모이제이션을 적용할 수 있는지를 따지고 난 후 사용하면 좋다.

---

< 11726 -  2xn 타일링 >

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

11726번: 2×n 타일링

풀이 : 

모든 경우의 수를 생각해보면 규칙을 찾을 수 있다. 

n=1일때) I

n=2일때) II, =

n=3일때) III, =I, I=

n=4일때) IIII, =II, I=I, II=, II=

...

2xn 사이즈의 직사각형을 채우려면 2x(n-1)과 2x(n-2)사이즈의 직사각형을 채우는 방법을 더하면 된다. 따라서 dp[n] = dp[n-1] + dp[n-2]이다.

#include <iostream>

using namespace std;

int main()
{

    int n;
    cin >> n;

    int dp[1001] = {0};
    dp[1] = 1;
    dp[2] = 2;

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

    cout << dp[n];

    return 0;
}

---

< 2749 -  피보나치 수 3 >

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

2749번: 피보나치 수 3

풀이 : 

일반적인 피보나치를 이용해서 풀면 n의 값이 너무 크기 때문에 시간 내에 답을 구할 수 없다. 이 문제는 피보나치의 속성을 몇 가지 알아야 풀 수 있다. 

- 피사노 주기 : 피보나치 수를 K로 나눈 나머지는 항상 주기를 가진다. (ex: 피보나치 수를 3으로 나누었을 때 주기는 8)

- 주기가 t라면 n번째 피보나치 수를 m으로 나눈 나머지는 n%t번째 피보나치 수를 m으로 나눈 나머지와 같다.

- m = 10^k일 때, k가 2보다 크다면 주기는 항상 15 * 10^k -1이다.

따라서 위의 속성들 중 세 번째를 이용하여 M = 1000000이므로 피사노 주기는 15 * 1000000 / 10 인 것을 알 수 있다. 그리고 두 번째 속성을 이용해서 구하려는 값은 n / 1000000 == n % t % 1000000임을 알 수 있다.

#include<iostream>
 
long long a[1500050];
int INF = 1000000;
 
void fibonacci() {
    a[0] = 0;
    a[1] = 1;
    for (int i = 0; i < 1500000; i++) {
        a[i + 2] = (a[i + 1] + a[i]) % INF;
    }
}
 
int main() {
    long long n;
    std::cin >> n;
    fibonacci();
    std::cout << a[n%1500000] << "\n";
 
}

---

< 11053 -  가장 긴 증가하는 부분 수열 >

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

11053번: 가장 긴 증가하는 부분 수열

풀이 : 

첫 번째 인덱스부터 검사하면서 dp리스트에 자신을 포함하여 만들 수 있는 부분 수열 크기를 저장한다. 현재 위치와 이전에 있는 원소를 크기 비교하여 크다면 현재 위치의 dp값에 1을 더해준다. 그리고 dp에 있는 값들 중 최댓값을 출력한다.

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

#pragma warning(disable: 4996)

using namespace std;

int main() {
    int T;
    int N, M, K, H;
    int X, Y;
    int answer = 0;
    
    int dp[1001];
    vector<int> v;
    cin >> T;

    for (int i = 0; i < T; i++) {
        cin >> K;
        v.emplace_back(K);
        int dp_max = 0;

        for (int j = 0; j < v.size(); j++) {
            if (v[i] > v[j]) {
                if (dp_max < dp[j])
                    dp_max = dp[j];
            }
        }
        dp[i] = dp_max + 1;
        answer = max(answer, dp[i]);
    }

    cout << answer << endl;

    return 0;
}

---

< 11049 -  행렬 곱셈 순서 >

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

11049번: 행렬 곱셈 순서

풀이 : 

A, B, C, D라는 행렬이 있을 때 A*B*C*D의 경우 A*B, B*C, C*D의 곱을 먼저 구하였다면 이후에도 그 전에 구한 값을 사용할 수 있다. 따라서 가장 적게 계산을 반복하는 경우를 DP배열에 저장하고 마지막에 출력한다. 

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define INF 1000000000

int N, r, c;
int sum[501], matrix[501][2], dp[501][501];

int main()
{
	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		cin >> r >> c;
		matrix[i][0] = r;
		matrix[i][1] = c;
	}

	for (int i = 1; i < N; i++)
	{
		for (int j = 1; i + j <= N; j++)
		{
			dp[j][i + j] = INF;
			for (int k = j; k <= i + j; k++)
			{
				dp[j][i + j] = min(dp[j][i + j], dp[j][k] + dp[k + 1][i + j] + matrix[j][0] * matrix[k][1] * matrix[i+j][1]);
			}
		}

	}

	cout << dp[1][N];


}