프로그래머스 피보나치 수 파이썬 풀이 및 해설

이번 포스팅에서는 프로그래머스의 피보나치 수 퀴즈를 파이썬으로 풀어 보겠습니다.

문제 출처 프로그래머스 : 프로그래머스에서 보기

풀이 깃허브에서 보기 : 깃허브로 이동

문제 설명

문제는 다들 아시는 피보나치 수 풀이 입니다. 프로그래밍 배우실때 한번쯤은 다 풀어봤을 유명한 수학 문제중에 하나죠. 

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수라고 할 수 있죠. 다들 무엇으로 배웠나요? 다들 재귀함수를 공부하면서 재귀함수로 풀었을 것으로 예상됩니다.  그럼 우선 재귀함수로 풀어보겠습니다.

논리적으론 맞지만 문제의 의도에 부합하지 않는 풀이

def fibo(n):
    if n < 3:
        return 1
    else:
        return fibo(n-1) + fibo(n-2)


print(fibo(1000))

정상풀이

def solution(n):
    fibo = []
    for num in range(0, n+1):
        if num == 0:
            fibo.append(0)
        elif num == 1:
            fibo.append(1)
        else:
            fibo.append(fibo[num - 2] + fibo[num - 1])

    return fibo[n] % 1234567

솔루션 및 해설