[프로그래머스] 피보나치 수열 - Python

 

def solution(n):
    answer = 0
    fibo = []
    for i in range(0, n+1):
        if i == 0 :
            fibo.append(0)
        elif i == 1:
            fibo.append(1)
        else :
            fibo.append( fibo[i-2] + fibo[i-1] )
    answer = fibo[len(fibo)-1] % 1234567
    return answer

https://programmers.co.kr/learn/courses/30/lessons/12945

코딩테스트 연습 - 피보나치 수

 

피보나치 수열을 재귀함수를 이용하여 구현하게 되면 시간초과 에러가 뜬다. 따라서 위와같이 구현하였다.

 

리스트에 수열 값들을 저장하고 꺼내오는 식으로 구현했다.

 

F(0) = 0

F(1) = 1

F(2) = F(0) + F(1) = 0 + 1 = 1

F(3) = F(1) + F(2) = 1 + 1 = 2

F(4) = F(2) + F(3) = 1 + 2 = 3

F(5) = F(3) + F(4) = 2 + 3 = 5 

...

0

1

1

2

3

5

3+5=8

11

19

30