[C언어] 백준 2747번: 피보나치 수

https://www.acmicpc.net/problem/2747

2747번: 피보나치 수

#include <stdio.h>
int main(){
	int n, memo[46] = {0, 1};
	scanf("%d", &n);
	for (int i = 2; i <= n; i++){
		memo[i] = memo[i-1] + memo[i-2];
	}
	printf("%d", memo[n]);
	return 0;
}

 

---

#include <stdio.h>
int fibo(int n){
	if (n < 2) return n;
	else return fibo(n-1) + fibo(n-2);	
}

int main(){
	int n;
	scanf("%d", &n);
	printf("%d", fibo(n));
	return 0;
}

위와 같이 피보나치를 재귀함수로 구현할 수 있지만, 재귀함수를 사용하면 이 문제에서는 시간 초과 또는 메모리 초과가 뜬다. 재귀함수는 호출할 때마다 스택(Stack)이 쌓이기 때문에 여러 번 호출될수록 수행 시간이 길어지고 메모리 사용량이 많아진다.