[C/C++] 백준 2748번 피보나치 수 2 동적 계획법(DP, Dynamic Programming) 풀이(+재귀, 반복알고리즘)

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 90보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

예제 입력 1

10

예제 출력 1

55

 

<재귀로 푼 코드>

#include<stdio.h>

int fibonacci(int n)
{
	if (n <= 2)
	{
		return 1;
	}



	return fibonacci(n - 1) + fibonacci(n - 2);
}

int main(void)
{
	int N;
	scanf("%d", &N);
	printf("%d", fibonacci(N));
}

 

시간 초과가 일어난 것을 보아하니 동적 계획법(DP, Dynamic Programming)을 이용하여 문제를 풀어야만 했다.

 

<Dynamic Programming 코드>

#include<stdio.h>

long long fibo_memo[100] = {0};
long long fibo(int n)
{

	if (fibo_memo[n] != 0)
		return fibo_memo[n];
	else
	{
		if (n == 0) return 0;
		if (n == 1 || n == 2) return fibo_memo[n] = 1;
		else
		{
			fibo_memo[n] = fibo(n - 2) + fibo(n - 1);
		}
		return fibo_memo[n];
	}
}

int main()
{
	int n;
	scanf("%d", &n);
	printf("%lld\n", fibo(n));


	return 0;
}

평소에 재귀방식으로 모든부분을 체크하는 방식이 꽤 유용하다고 생각했었는데 시간 복잡도를 생각하면 2^n 형태로 올라가게되어 매우 비효율적인 부분이 있음을 알게 되었고 또한 이러한 문제점을 해결하기 위해 동적계획법을 공부하였다. 처음에는 코드가 이해가 가지 않아 이해하는데 시간이 좀 걸렸다.

fibo_memo배열을 0으로 초기화 한 뒤 if (fibo_memo[n] != 0) return fibo_memo[n]; 

이렇게 해주는 이유는 알겠으나 구글링 하던 중 if (fibo_memo[n]) 이런식으로 조건문이 들어있어야 할 곳에 배열만 딸랑 있는게 아직도 잘 이해가 안간다. 대충 이것저것 대입해보고 실험해보니 fibo_memo배열이 초기화되었는지 안되었는지 판별하는 것 같은데 정확하지는 않다(해당 인덱스의 배열 값이 NULL인지 아닌지는 판별하는 건 아닌것 같다).  

 

<반복 알고리즘 이용>

#include <stdio.h>

long long dp_array[100];

long long fibonacci_dp(int n) {

	int i;

	dp_array[0] = 1;
	dp_array[1] = 1;

	for (i = 2; i < n; i++) {
		dp_array[i] = dp_array[i - 1] + dp_array[i - 2];
	}
	return dp_array[n - 1];
}


int main() {

	int i, N;
	scanf("%d", &N);
	printf("%lld", fibonacci_dp(N));

	return 0;
}