Fibonacci numbers(피보나치 수)

Fibonacci numbers 

위키백과 - 피보나치 수

위 식과 같이 수를 나열하면(첫 번째는 0)  

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 

파이썬 재귀함수를 배울 때 재귀함수로 푸는 방법을 배웠었다. 

def Fibo(n):
    if n == 0:
        return 0
    elif n == 1 :
        return 1 
    else: 
        return Fibo(n-2) + Fibo(n-1)


print([Fibo(i) for i in range(12)]) # [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]

하지만 프로그래머스에서 런타임 오류가 발생하였다. 

그래서 위키백과에서

위 식 외에 피보나치의 급수 공식 

을 수정 해서

이 식을 만들어 보았다 저번 등차수열 알고리즘 문제에서 단수 For문 사용하기 보다 등차 수열 합을 했던 것 처럼 

식을 코드로 풀어 보았다. 

def solution(n):
    a = [0,1,1]
    if n < 2 :
        k = n 
    else : 
        k = n-2 
    answer= 0 
    
    for i in range(k+1):
        answer += a[i]
        a.insert(i+2,answer +1)
    return (answer +1) % 1234567

물론 for문을 돌렸지만 다행이 런타임 오류는 나오지 않았다. n이 2보다 크다면,

두 차례 앞의 피보나치 수를 추가하면서 for 문을 돌려 결과를 계산하는 식이다.

return 에 % 1234567 붙힌 이유는 알고리즘 문제에 조건으로 나오는 것이다. 항이 계속 될 수록 숫자가 너무 커지기 때문에 붙혀 준 것 같다. 

문제를 푼 후 다른 사람의 풀이를 보았을 때 참 쉽게 풀었다는 것을 알 수 있었다. 

이 후 소개드릴 코드는 프로그래머스 다른 사람 풀이에서 본 코드를 그대로 가져왔다. 

def fibonacci(n):
	a,b = 0,1
    for i in range(n):
    	a,b = b,a+b
    return a 
    
print(fibonacci(11)) # 89

파이썬의 특징(장점)인 a,b = b,a+b 이 부분이 중요한데 a = b 가 되고 b = a+b 가 되는데, 이게 동시에 일어나다 보니 

a + b 는 변경 되기 전 a와 b 의 더하기 a 는 변경 되기 전 b 가 된다고 생각하면 된다. 

이 부분은 아래 식을 참고해서 작성 한 것이다. 

이 코드는 내 풀이 처럼 리스트 저장도 따로 하지 않고 재귀함수 풀이 처럼 큰 수 때 함수를 계속 계산 하는 

메모리가 줄어들기 때문에 좋은 코드라고 생각 한다. 

Reference 

피보나치 수 : https://ko.wikipedia.org/wiki/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98_%EC%88%98