[BOJ] 백준 2747 피보나치 수

문제 링크

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

피보나치 수열은 보통 점화식으로 다음과 같이 표현된다.

$$f(n) = f(n-2) + f(n-1), (f(0) = 0, f(1) = 1)$$

이를 재귀함수로 구현하면

	int fibo(int n) {
	if (n == 0)
	return 0;
	if (n == 1)
	return 1;
	return fibo(n - 2) + fibo(n - 1);
	}

view raw fibo.cpp hosted with ❤ by GitHub

이렇게 되고, 위의 코드에서 $n = 6$인 경우 다음 그림처럼 함수가 전개된다.

재귀함수가 $n$을 인자로 호출되면 그 함수는 $n - 1$과 $n - 2$를 인자로 함수를 호출하고, 호출된 각 함수가 계속해서 함수를 두 개씩 호출하게 된다. 결국 시간복잡도가 $O(2^N)$이므로 n 제한이 $n <= 45$인 해당 문제의 경우 제한시간 내에 답을 구할 수 없다.

이를 해결하기 위해 반복해서 호출되는 부분에 주목해야한다.

네모 친 부분 트리들은 해당하는 $n$에 대해 최초로 답을 구했을 때, 어딘가에 답을 적어둔다면 다시 만났을 때 그 답을 활용 할 수 있으므로 더는 전개할 필요가 없게 된다. 이런 기법을 $Memoization$이라 하며,

이를 이용해 문제를 푸는 방식을 $Dynamic\,Programming$(동적계획법)이라 한다.

동적 계획법을 더 자세히 알고싶으면 다른 블로그를 활용하자.

동적 계획법을 이용하면 함수는 다음과 같이 호출된다.

어떤 $n$에 대해 최초 한번씩만 함수가 실행되므로 시간복잡도는 $O(N)$이다.

정답 코드

Bttom-up

	#include <iostream>
	using namespace std;
	int n, d[50];
	int main() {
	d[1] = 1;
	for (int i = 2; i <= 45; i++) {
	d[i] = d[i - 1] + d[i - 2];
	}
	cin >> n;
	cout << d[n];
	}

view raw 2747(bottom-up).cpp hosted with ❤ by GitHub

Top-down

	#include <iostream>
	using namespace std;
	int n, d[50] = {0, 1};
	int fibo(int n){
	if (n == 0) return 0;
	if (n == 1) return 1;
	if(d[n] != 0)
	return d[n];
	d[n] = fibo(n - 2) + fibo(n - 1);
	return d[n];
	}
	int main() {
	cin >> n;
	cout << fibo(n);
	}

view raw 2747(top-down).cpp hosted with ❤ by GitHub