[programmers] 피보나치 수, Big(O)

프로그래머스 Lv.2 피보나치 수

이 문제는 사실 매우 간단한 문제이지만,
생각 정리가 필요한 문제라고 생각하여 리뷰를 하기로 하였다.

처음 작성한 코드 - runtime error

def solution(n):
	def fibo(x):
    	if x==0:
        	return 0
        elif x==1 or x==2:
        	return 1
        else
        	return fibo(x-1) + fibo(x-2)

	return fibo(n) % 1234567        

피보나치 수를 재귀함수로 구현하였다.
가장 직관적이고 간단한 표현식이라고 생각하였다.
하지만 runtime error 문제가 발생하였다.

이 경우, n=5에 대한 계산을 할때 15회의 계산 횟수가 필요하다.

fibo(5) = fibo(4) + fibo(3) ............. f(5) : 1회
	fibo(4) = fibo(3) + fibo(2) ......... f(4) : 1회
    fibo(3) = fibo(2) + fibo(1) ......... f(3) : 2회
    fibo(2) = fibo(1) + fibo(0) ......... f(2) : 3회
        fibo(1) ......................... f(1) : 5회
        fibo(0) ......................... f(0) : 3회

이 함수의 시간복잡도는 $2^0$ + $2^1$ + ... + $2^(n-3)$
(아니 대체 어떻게 표현하는거야???ㅋㅋㅋ)

아무튼, 정리하자면 시간복잡도는 $O(2^n)$ 이다.

$O(2^n)$ 은 매우 좋지 않은 시간복잡도를 가진다!!

---

이 문제를 해결하기 위해 코드를 수정했다.

수정한 코드 - 성공

def solution(n):
    # 재귀함수로 하면 절대 구해지지가 않는다...! runtime error
    fib_init = [0,1,1] # 피보나치 수열의 초기 값

	for i in range(3, n+1):
        fib_init.append((fib_init[i-2] + fib_init[i-1]))

	answer = fib_init[-1]

    return answer % 1234567

3 이상의 n이 주어지면 fib_init에 저장된 초기 값에 이어서
배열 연산을 진행하고, n회까지 진행했을 때 마지막 원소의 값이
원하는 값이 된다.

얼핏 보기에는 for문을 돌려야 하고, 배열에 추가해야 하고..
효율성이 좋은가? 라고 생각이 들었다.

하지만 이 계산의 경우 시간 복잡도는 $O(n)$ 이다!!
실질적으로 n이 증가함에 따라 반복횟수는 1밖에 되지 않는다.

시간 복잡도는 곧 돈과 연결된다고 들었다.
매우 중요한 개념이니, 문제를 풀때 계속 생각하는 습관을 들이도록 하자.