11강 - 다이나믹 프로그래밍 (Dynamic Programming)

1. DP

1) 정의

1> 큰 문제를 작은 문제로 나눠 풀 때 작은 문제들이 같은 문제라면

2> 그 문제들을 매번 재계산하지 않고 값을 저장해두었다가 재사용하는 기법

2) 특징

1> 단순 분할 정복과는 다르게 동일한 문제를 다시 풀지 않습니다.

2> Memoization을 통해 이미 계산한 결과는 array에 저장함으로써 나중에 동일한 계산이 필요한 경우 단순 return합니다.

 

 

2. 예시 (피보나치 수열)

#include <iostream>
using namespace std;

int memo[100];

int fibonacci(int x)
{
	if (x == 1) return 1;
	if (x == 2) return 1;
	if (memo[x] != 0) return memo[x]; // 기록한 적이 있다면 기록한 것을 출력
	return memo[x] = fibonacci(x - 2) + fibonacci(x - 1);
}

int main()
{
	int n;
	cin >> n;
	cout << fibonacci(n);
}