[DP] 동적 계획법 알고리즘 c++ 설명

목차

 

DP(다이나믹 프로그래밍)

메모리를 적절히 사용하여 시간 복잡도를 비약적으로 단축시킬 수 있는 방법이다.

일반적으로 하향식 또는 상향식으로 구현된다.

 

 

 

상향식 (타뷸레이션)

• 하위의 문제를 이용하여 더 큰 문제의 정답을 풀어나가는 방법이다.
• 결과 저장용 리스트나 사전을 DP 테이블이라고 한다.
• 보통  for문을 이용한 구현 방식이다.

 

 

하향식 (메모이제이션)

• 큰 문제에서 하위 문제로 접근하여 하위 문제에 대한 정답을 계산 했는지 확인하며 푸는 방식이다.
• 보통 while문을 이용한 구현 방식이다.

 

 

 

다이나믹 프로그래밍의 조건

• 최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아 큰 문제를 해결한다.
• 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결한다.

 

 

 

 

 

 

 

 

 

 

이미지 출처: https://fullmoon1344.tistory.com/67

 

 

 

 

대표적인 예: 피보나치 수열

#include <iostream>
#include <vector>
using namespace std;
//재귀함수로 구현
int fibo(int n);

int main()
{
	int n;
	cin >> n;
	cout << fibo(n);
}
int fibo(int n)
{
	int result;
	if (n < 2) 
	{
		return n;
	}
	else
	{
		result= fibo(n - 1) + fibo(n - 2); 
	}
	return result;
}

 

 

재귀함수로 구현했을 때 문제점

예를 들어 F(6)을 계산할 때 F(2)가 여러번 호출되게 된다.

이 수가 점점 커진다고 생각하면 불필요한 연산을 수 없이 많이 하게 된다.

따라서 하양식을 통해 메모이제이션을 하여 해결할 수 있다.

 

 

 

하향식을 통해 해결한 피보나치 수열

#include <iostream>
#include <vector>

using namespace std;
//하양식으로 구현
int fibo(int n);
vector<int> v(1000, 0);
int main()
{
	int n;
	cin >> n;
	cout << fibo(n);
}
int fibo(int n)
{
	
	if (n < 2)
	{
		return n;
	}
	else
	{
		if (v[n] != 0)  //이미 계산한 경우 기존 것 사용
			return v[n];
		v[n] = fibo(n - 1) + fibo(n - 2);  //없을 경우 계산하고 넣어줌
		return v[n];
	}
	
}

 

 

 

 

상향식을 통한 피보나치 수열

#include <iostream>
#include <vector>

using namespace std;
//상향식으로 구현

vector<int> v(1000, 0);
int main()
{
	int n, i;
	cin >> n;
	v[1] = 1;
	v[2] = 1;
	for (i = 3; i <= n; i++) {
		v[i] = v[i - 1] + v[i - 2];
	}
	cout << v[n];

}