[BOJ] 백준 2747 피보나치 수

문제 링크

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

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

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

이를 재귀함수로 구현하면

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

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

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

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

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

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

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

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

정답 코드

Bttom-up

Top-down