[알고리즘]#5_동적 계획법

 

[알고리즘]#5_동적 계획법

 

동적 계획 알고리즘에 대해 알아보겠습니다.

 

---

 

Overview

 

1. 개념
2. 예제

 

#0. 개념

1. 동적 계획법(Dynamic Programming)

• 동적 계획법은 최적화 문제를 해결하는 데 사용되는 알고리즘 디자인 기법 중 하나입니다.
• 동적 계획법은 입력 크기에 따라 중복되는 하위 문제를 재귀적으로 해결하고, 이 결과 값들을 기억하는 것으로 중복 계산을 피해 최적화를 수행하고 효율적으로 최적해를 찾아냅니다.

 

2. Memoization

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

long long dp[101] = { 1, 1, };

long long Fib(int n)
{

	if (n <= 1)
		return n;
	
    	// #1. dp 배열에 이미 결과 값이 있을 경우, 중복 계산을 방지합니다.
	if (dp[n] != 0)
		return dp[n];

	// #2. Memoization 기법을 통해 부분 문제의 결과 값들을 기억해둡니다.
	dp[n] = Fib(n - 1) + Fib(n - 2);

	return dp[n];

}

int main()
{
	cout << Fib(4) << endl;
	cout << Fib(10) << endl;

	return 0;
}

 

Details

 

• Memoization은 동적 계획법의 한 기법으로, 중복 계산을 방지하기 위해 이전의 결과 값들을 기억해 두어 재활용하는 것을 의미합니다.
• Memoization은 분할 정복 기법과 비슷하지만, Memoization은 부분 문제의 해를 저장하여 중복 계산을 방지하는 데 초점을 맞춥니다. 

 

2. 동작 방식

1. 중복되는 하위 문제 식별 : 주어진 문제를 하위 문제들로 분할합니다. 분할된 하위 문제들은 원래 문제와 구조적으로 동일하지만 입력 크기가 더 작습니다.
2. 분할된 하위 문제들의 재귀적 해결 : 가장 작은 하위 문제부터 재귀적으로 해결하며, 이렇게 해결된 결과는 저장해 두어 중복 계산을 방지합니다.
3. 최적해 도출 : 모든 하위 문제들을 재귀적으로 해결하고, 주어진 문제의 최적 해를 구하기 위해 이전에 기억해둔 결과 값들을 결합하여 활용합니다.

 

#1. 예제

1. 피보나치 수열 

#include <iostream>
using namespace std;

long long f[41];

int main()
{
    f[1] = f[2] = 1;
    for (int i = 3; i < 41; i++)
    {
        f[i] = f[i - 1] + f[i - 2];
    }

    int N;
    cin >> N;

    cout << f[N] << " " << N - 2 << endl;
}

 

Details

 

• 입력 값이 최대 41이라고 가정하고, 동적 계획법을 활용해 피보나치수열의 n번째 항을 구하는 코드입니다.
• 피보나치수열의 첫 번째, 그리고 두 번째 항은 항상 1이기 때문에 Memoization을 수행하는 long long 타입의 배열은 1, 그리고 2번 인덱스에 1을 저장해 둡니다. 그리고, 3부터 41까지 반복문을 수행하며 결과 값을 차례대로 저장합니다.
• 최종적으로 배열의 n번 인덱스는 피보나치 수열의 n번째 항을 갖게 됩니다.

 

2. 파도반 수열

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

long long dp[101] = {0, 1, 1, 1};

long long PadovanDP(int n)
{
    for(int i=4; i<= n; i++)
    {
        dp[i] = dp[i-2] + dp[i-3];
    }

    return dp[n];
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    
    int T, N;
    cin >> T;
    for (int i = 0; i < T; i++)
    {
        cin >> N;
        cout << PadovanDP(N) << '\n';
    }
}

 

Details

 

• 파도반 수열을 동적 계획법을 활용해 구현하는 코드입니다. 
• 파도반 수열의 점화식은 P(n) = P(n-2) + P(n-3), n >= 4 그리고, P(n) = 1, n = 1, 2, 3입니다.
• Memoization을 수행하는 배열 dp [101]의 1, 2, 그리고 3번 인덱스는 1로 초기화합니다. 그리고, 인자로 전달받은 숫자 n까지 반복문을 수행하며 dp [i] = dp [i-2] + dp [i-3]을 수행합니다.