[프로그래머스 LV.2] 피보나치 수

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

프로그래머스

 

전체 코드

import sys
sys.setrecursionlimit(100000)

from collections import defaultdict

def solution(n):
    d = defaultdict(int)
    d[0] = 0
    d[1] = 1
    d[2] = 1
    
    def fibo(n):
        if n <= 2:
            return d[n]
        else:
            if not d[n]:
                d[n] = fibo(n-2) + fibo(n-1)
            return d[n]
        
    return fibo(n) % 1234567

 

알고리즘 설명

재귀함수와 defaultdict를 사용하였다.

 

코드 설명

기존 피보나치수열을 구현하는 것처럼 코드를 구현했을 때, 시간 초과와 런타임 에러가 발생했다.

이를 해결하기 위해 다음과 같은 방법을 사용하였다.

 

1. 시간 초과 해결

defaultdict를 활용하여 피보나치수열의 값을 저장하였다. 이를 통해, 이후 이미 계산했던 피보나치 수가 필요할 때 defaultdict에서 꺼내와 사용할 수 있었다. 이것으로 재귀함수를 호출하는 횟수를 줄일 수 있었고, 시간 초과 문제를 해결하였다.

 

2. 런타임 에러

현재 문제에서 n의 범위는 100,000 까지이다. 만약 100,000을 인자로 fibo 함수를 실행하게 된다면 재귀 최대 깊이가 Python3 기준 최대 재귀 깊이인 1000을 넘어갈 것이다. 따라서 sys 라이브러리를 import 한 후, setrecursionlimit 메소드를 사용해 재귀 최대 깊이를 100,000으로 설정하였다. 이것으로 런타임 에러를 해결할 수 있었다.