동적 계획법

2747번: 피보나치 수 (acmicpc.net)

 

피보나치는 수는 0과 1로 시작하며 2번째 부터는 앞의 두 수를 더해서 이어 나갑니다.

즉 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 --------으로 이어집니다.

 

N번째 피보나치 수를 구하기를 여러번 반복하게 되는 상황에서

매번 0부터 N까지 수를 구해나가면 굉장히 비효율 적입니다.

 

그렇기에 문제를 반복되는 작은 문제로 바꿀 수 있어야합니다.

또한 문제들을 DP 테이블에 저장하여 재사용할 수 있게하여 속도를 높여야합니다.(메모이제이션 기법)

이러한 것을 동적계획법이라 부르는데 톱-다운 방식과, 바텀-업 방식으로 구현할 수 있습니다.

 

 

톱 - 다운 방식

#include <iostream>
#include <vector>

using namespace std;

static int N;
static vector<int> D;

int fibo(int n)
{
	if (D[n] != -1) {
		return D[n];
	}

	return D[n] = fibo(n - 2) + fibo(n - 1); 
}

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

	cin >> N; 
	D.resize(N + 1, -1);
	 
	D[0] = 0; 
	D[1] = 1;
	  
	
	fibo(N);
	cout << D[N] << "\n"; 
}

 

바텀 - 업 방식

#include <iostream>

using namespace std;

static int N;
static long mod = 1000000000; 
static long D[1000001];
int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); 
	cout.tie(NULL);

	cin >> N; 

	D[0] = 0;
	D[1] = 1;
	  
	for (int i = 2; i <= N; i++) {
		D[i] = D[i - 1] + D[i - 2];  
	}
	cout << D[N] << "\n"; 
}

톱-다운 방식의 경우 재귀의 깊이가 '매우매우매우' 깊어지면 런타임 에러가 발생할 수 있다는 문제가 있습니다.

보통의 상황에서는 그정도로 재귀를 깊게할 일이 없기에 코딩테스트를 할때 신경 쓸 부분은 아니지만 재귀할 일 자체가 없는 바텀-업 방식이 조금 더 안전하다 라고 말합니다.

그냥 본인이 좋은거 쓰면 됩니다.\

 

 

좋은 예시 문제

2193 이친수 (조합론, 동적 계획법) [Silver III]

 

1463 1로 만들기 (동적 계획법) [Silver III]

\