메모이제이션을 활용한 피보나치 함수

문제설명

재귀함수를 통한 피보나치 함수인데 기존의 방식을 활용하면 너무 오랜 시간이 걸려서 메모이제이션을 활용해보았습니다.

​

작동 순서

다른 피보나치 함수와 방법이 동일하지만 메모이제이션을 활용해서 이미 구한적이 있는 숫자는 저장해놓았다가 필요해진 경우 다시 계산하지 않고 함수에서 바로 꺼내오는 방식입니다.

​

소스코드

import sys
limit_number = 15000
sys.setrecursionlimit(limit_number)
fib = [0] * 6437


def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        if fib[n] == 0:
            fib[n] = fibonacci(n - 1) + fibonacci(n - 2)
            return fib[n]
        else:
            return fib[n]


print(fibonacci(int(sys.stdin.readline())))