1003 - 피보나치 함수

보통 피보나치는 문제의 설명에 적혀있듯이 재귀적으로 작성할 수 있다.

return fibonacci(n‐1) + fibonacci(n‐2); 와 같이 말이다.

하지만 함수의 호출 스택의 한계를 무시한다고 생각해도 일단 중복되는 호출이 굉장히 많다.
f(3) = f(2) + f(1) = f(1) + f(0) + f(1) = f(1) + f(0) + f(0) 과 같이 f(3)만 하더라고 f(1)을 여러번 부른다. 이러면 시간복잡도는 지수함수가 되는데, 메모리는 둘째치고 시간이 굉장히 오래걸린다.

즉, 이 문제는 재귀를 사용하지 않고 비재귀적(iterative)하게 작성할 수 있는가가 핵심이다.

원리만 잘 파악하면 피보나치는 변수 2개로 해결할 수 있다.

먼저 a = 0, b = 1 로 시작한다. 그리고 다음번의 b 가 a + b 가 되고, 다음번의 a 는 바뀌기 전의 b 가 된다. 이 행동을 반복하면, b는 N번째 피보나치 수가 된다.

예를 들면, 순서대로 a b 라고 할 때 1~5번의 반복이 일어날 동안 변수의 상황은 아래와 같다.

0 1
1 1
2 1
3 2
5 3

예시를 잘 보면 문제를 해결할 수 있을 것이다.