즐겁게, 코드

[백준 온라인 저지 - 문제 링크] N번째 피보나치 수를 구하는 문제입니다. 다만 N의 범위가 0 ~ 1백만 사이로, 꽤나 큰 피보나치 수를 구해야 합니다. 우선 이 문제는 파이썬 + 재귀 조합으로는 풀 수 없습니다! C++이나 자바 등의 언어에서는 어떤지 모르겠지만, 파이썬은 기본적으로 1000번까지의 *재귀 호출만을 허용합니다. 따라서 메모이제이션을 활용하는 재귀 함수 코드로는 런타임 에러를 피할 수 없게 됩니다. (* sys 모듈을 불러온 후 sys.setrecursionlimit() 함수를 활용하면 최대 재귀 깊이를 조정할 수 있긴 합니다만, 이 문제에서는 메모리 초과 에러에 걸리게 됩니다.) 그래서, 이 문제는 잠깐 초심(?) 으로 돌아가 단순 for문을 활용해 해결할 수 있습니다. [정답 코드..

혹시 피보나치의 수를 구하는 알고리즘을 알고 계신가요? 아마 많은 분들이 재귀함수를 사용하는 알고리즘을 떠올릴 것입니다. N = int(input()) def fib(N): if N == 0 or N == 1: return N return fib(N - 1) + fib(N - 2) print(fib(N)) # input output time # 10 55 0.00092s # 5 5 0.00018s # 100 한없이 긴 시간이 소요됩니다... 얼핏 보면 완벽해 보이는 알고리즘이지만 여기에는 함정이 하나 숨어있는데요, 잠깐 5번째 피보나치 수를 구하는 과정을 그림으로 소개하자면 아래와 같습니다. 5번째 피보나치 수는 4번째 피보나치 수와 3번째 피보나치 수를 더한 결과이며, 4번째 피보나치 수는 3번째 + ..