[BOJ] 1003 피보나치 함수 - 동적 계획법

BOJ 1003 피보나치 함수

동적계획법을 사용한다는 것은 이전의 연산결과를 통해 다음의 연산결과를 구해내겠다는 것이다.

위의 피보나치 함수의 예는 아주 간단하고도 대표적인 예이다.

위 함수를 F(N) 이라고 부른다고 하자.

F(N) 은 F(N-1) 과 F(N-2) 를 호출한다.

그렇다면 F(N-1) 은 F(N-2)와  F(N-3)을 , F(N-2)는 F(N-3)과 F(N-4)를 호출 한다.

피보나치 함수는 또 다른 피보나치 함수를 2개 호출 한다.

위의 조건을 보면

F(1)일때는 1을 출력한다.

F(0)일때는 0을 출력한다.

그러면 F(2)는 ?? 1과 0을 1개씩 출력하는 것 이다.

조금만 더 계산해보면 F(3)은 F(2)의 결과 (1 과 0 각각  1개씩) 을 출력하되 F(1)의 것 (1만 1개)을 출력한다.

F(4) 의 경우는 ? F(3)의 결과값에 , F(2) 결과값이 합쳐진 것이 결과값이 된다.

이전의 값을 미리 계산해야만, F(N) 을 구할 수 있다.

따라서 반복문을 돌리면 F(N)을 낮은 인덱스 부터 차례대로 구하게되면 원하는 값을 구할 수 있다.

#include <iostream>
int fibonacciZeroNum[41];
int fibonacciOneNum[41];

using namespace std;





int main()
{
	fibonacciOneNum[0] = 0;
	fibonacciOneNum[1] = 1;

	fibonacciZeroNum[0] = 1;
	fibonacciZeroNum[1] = 0;

	for (int i = 2; i <= 40; i++)
	{
		fibonacciOneNum[i] = fibonacciOneNum[i - 2] + fibonacciOneNum[i - 1];
		fibonacciZeroNum[i] = fibonacciZeroNum[i - 2] + fibonacciZeroNum[i - 1];
	}

	int T = 0;
	cin >> T;
	int N = 0;
	for (int i = 0; i < T; i++)
	{
		cin >> N;
		if (N == 1)
			cout << fibonacciZeroNum[1] << " " << fibonacciOneNum[1] << endl;
		else if (N == 0)
			cout << fibonacciZeroNum[0] << " " << fibonacciOneNum[0] << endl;
		else
			cout << fibonacciZeroNum[N] << " " << fibonacciOneNum[N] << endl;
	}
	
	

	return 0;




}

 

이건 진짜 문득 든 생각인데

Dynamic Programming과 Memoization과의 차이가 여기에 있는 것이 아닐까한다.

(어디까지나 주관적이다.)

이전의 계산결과를 저장해두고, 다음 연산에 이용하는것은 둘의 개념이 같다.

Dynamic Programming의 경우에는 이전의 값을 구하지 않으면 다음의 값을 구할 수 없다.

 

순차적으로 건너온 이전의 값을 몰라도 답을 구할 수 있는 문제가 있다.

허나 중복해서 계산하는것이 불필요하므로 미리 저장하고 싶다. 

이 경우가 Memoization이다. 

 

한가지 아주 간단한 예시를 들어보자.

 

수열의 합을 구할때 어떻게 구할 것인가?

위와 같은 수열이 있을때, 이 수열을 Arr이라고 부르자.

그리고 Arr의 어떠한 index A에서 index B까지의 모두 합친 값을 Sum(A,B)라고 부른다고 하자.

 

그렇다면 단순하게 A에서 B까지 Arr의 원소에 접근해서 값을 더해나가면 답을 그냥 구할 수 있다.

허나 다음번 시도때는 Arr에 원소에 또 접근을 해야 되겠다. 반복해서 접근하니 이것은 손해다.

그래서 Sum(0,N)을 전부다 구해둔다 . (Memoization)

그리고 나서 그래서 Sum(0,B) - Sum(0, A-1)로 구한다. 이러면 배열의 원소에 반복 접근 하진 않는다.

허나 Sum(0,B)를 모른다고 해서 답을 못구하냐 그것도 아니지 않은가?

 

근데 Dynamic이란 단어를 배열에 미리 계산해둔 결과를 동적으로 넣어준다는

뜻으로 받아 들이면 Memoization은 Dynamic Programming 안에 포함되는 개념이다.

 

이런 고민들이 가장 쓸데가 없는 고민인것 같기도 하다?

이름이야 어쨌던 적절하게 사용해서 빠르고 안정적인 코드만 잘 구현해내면 그만이다.