[프로그래머스 Lv.2] 피보나치 수 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12945

프로그래머스

풀이

피보나치 문제는 전형적인 DP(Dynamic Programming) 문제이다. DP의 메모이제이션을 활용하여 재귀함수 속에서 이미 계산된 n에서의 피보나치를 저장해두고, n에서의 피보나치 재귀 함수를 호출하면 재귀함수 없이 즉각적으로 저장이 된 해당 수를 반환하도록 하여 재귀함수의 호출 수를 줄임으로써 시간 초과 없이 문제를 해결할 수 있다. 

import sys
sys.setrecursionlimit(int(10e8)) # 재귀 깊이 한계 증가

answer = [0 for _ in range(100001)] # 해당 인덱스에서의 피보나치 수를 저장할 배열

def get_pibo(n): # n에서의 피보나치 수를 반환하는 재귀함수
    if answer[n] != 0: # 이미 계산하여 저장된 수라면
        return answer[n] # 즉시 그 값을 반환
    pibo = (get_pibo(n-1) + get_pibo(n-2)) # n의 피보나치 수 = n-1의 피보나치 수 + n-2의 피보나치 수
    answer[n] = pibo # n에서의 피보나치 수를 저장하여 추후에 다시 n의 피보나치 수를 호출한다면 즉시 반환될 수 있도록 함
    return pibo
    

def solution(n):
    answer[1] = answer[2] = 1 # 1과 2의 피보나치 수는 1임
    return get_pibo(n) % 1234567