다이나믹 프로그래밍

: 언제 사용할까??
한번 해결한 문제를 다시 해결하고 싶지 않을때 사용한다.
1. 큰 문제를 해결하기 위해 작은 문제로 나뉠때
2. 동일한 작은 문제를 반복적으로 해결해야 할때
메모이제이션을 이용하자.

메모이제이션

: 한번 계산된 결과를 메모리 공간에 메모하는 기법이다.

• 같은 문제가 다시 호출되면 메모했던 결과를 사용하자
• 값을 기록한다는 점에서 캐싱이라고 한다.

피보나치 수열

: 다음과 같은 형태의 수열이다.
1,1,2,3,5,8,13,21,34,55.....

• 다이나믹을 사용하면 시간복잡도는 지수시간의 복잡도를 확보할수가 있다.
  but 반복문 사용하면 엄청난...ㅜㅜ..

• 풀이 : 점화식을 만들어서 접근하도록 하자!

(중요!)
1) 그냥 재귀

#include <iostream>

using namespace std;

int Fibo(int index)
{
	if (index == 1 || index == 0)
		return 1;
	
	return Fibo(index -1) + Fibo(index - 2);
}


//while 문으로 풀어보자! 
int main(void)
{
	cout << Fibo(9);

	return 0;
}

2) 바텀업 풀이
: 반복문 + 메모이

int main(void)
{
	memo[0], memo[1] = 1;

	for (int i = 2; i < 100; i++)
	{
		memo[i] = memo[i - 1] + memo[i - 2];
	}

	cout << memo[10];

	return 0;
}

3) 탑다운 풀이
: 재귀 + 메모이

#include <iostream>

using namespace std;

int memo[100];

int Fibo(int index)
{
	if (index == 1 || index == 0)
		return 1;
	
	if (memo[index] != 0)
		return memo[index];

	memo[index] =  Fibo(index -1) + Fibo(index - 2);
	return memo[index];
}


int main(void)
{
	cout << Fibo(9);

	return 0;
}

규칙성을 찾아 점화식을 만드는 것이 중요하다.

분할 정복 vs 다이나믹 프로그래밍

: 큰 문제를 작은 문제로 나눠야 할때 두개를 사용해 풀어야겠다
1) 분할은 부분 문제가 다른 부분에 영향을 안미칠때
2) 다이나믹은 부분 문제가 다른 부분문제에 영향을 끼쳐야 할때 사용한다.

다이나믹으로 문제 접근하기

: 페이지 216