[백준/BOJ] 4150번 - 피보나치 수 (파이썬)

문제 링크

 

코딩하기 전 생각하기

'''
메모이제이션을 활용하는 피보나치 재귀함수를 선언하자.
'''

 

---

 

코드

import sys
sys.setrecursionlimit(10**6)

memo = {}
def fib(n):
    if n == 1:
        return 1
    if n == 2:
        return 1
    if n in memo:
        return memo[n]
    memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]
    
n = int(input())
print(fib(n))

 

---

 

느낀점

 

이 문제를 통해서 메모이제이션이라는 개념에 대해서 알 수 있었다.

이 방식의 시간복잡도는 O(N)이다. 다음 링크를 참고하였다.

https://www.acmicpc.net/blog/view/28 

피보나치 수를 구하는 여러가지 방법

또한 파이썬에서 재귀 깊이에 따른 런타임 에러가 발생하여서 1, 2줄에 있는 코드를 추가하였다. 다음 링크를 참고하였다.

https://www.acmicpc.net/help/rte/RecursionError 

런타임 에러 도움말 (RecursionError)

정말 유익한 문제다.

 

(주의) 기록용으로 작성한 글입니다. 코드가 허접하거나 알고리즘의 효율이 낮을 수 있습니다.

댓글 환영합니다!