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

Link

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

 

Solution

필자는 해당 문제를 메모이제이션을 활용하여 해결하였다.

하지만 채점에서 몇개가 런타임에러가 발생하여 테스트 케이스에 100000을 추가해보았고 그 결과 재귀함수의 최대 재귀한도 깊이가 초과(RecursionError: maximum recursion depth exceeded in comparison)한다는 것을 파악하였다. 이에 sys.setrecurtionlimit()을 활용해 재귀한도를 늘려주어 해당 문제점을 해결하였다.

import sys
sys.setrecursionlimit(150000)

def fibo(n, arr):
    if n in [1, 2]:
        return 1

    if arr[n] != 0:
        return arr[n]
    else:
        arr[n] = fibo(n - 1, arr) + fibo(n - 2, arr)
        return arr[n]

def solution(n):
    if n in [1, 2]:
        return 1

    d = [0] * (n + 1)
    d[1] = 1
    d[2] = 1

    fibo(n, d)

    return d[n] % 1234567

🔑 key point: Dynamic Programming, Memoization
📌 Tip: sys.setrecursionlimit()

 

Other Solution

def solution(n):
    fibo = [0, 1]

    for i in range(2, n + 1):
        fibo.append((fibo[i - 2] + fibo[i - 1]) % 1234567)

    return fibo[-1]

🔑 key point: fibo[i - 2] + fibo[i - 1]