Python에서 재귀와 메모이제이션으로 피보나치 구하기
이 레슨에서는 재귀로 피보나치 수를 계산하고, 메모이제이션으로 이미 구한 결과를 다시 계산하지 않게 합니다.
소개
어떤 문제를 해결하나요
피보나치 수열을 재귀로 정의하면 코드는 아름답지만 엄청나게 느립니다. 40번째 항을 구하는 동안 똑같은 작은 계산을 수억 번이나 되풀이합니다. 메모이제이션(memoization)은 코드 한 줄로 이 문제를 해결합니다. 동적 계획법의 핵심 아이디어도 함께 배울 수 있습니다.
일상 속 비유
메모이제이션은 푼 답을 모두 공책에 적어 두는 학생과 같습니다. fib(5)를 또 물어보면 다시 풀지 않고 공책에 적힌 답을 읽습니다. 어떤 질문이든 딱 한 번만 풉니다.
@cache📓 답을 적어 두는 공책 준비하기fibonacci(number - 1) + fibonacci(number - 2)🧮 더 작은 질문 두 개로 풀기if number < 2: return number🛑 처음 두 답은 이미 알고 있음fibonacci(10)⚡ 작은 답은 모두 한 번씩만 계산: 빠름메모이제이션은 함수를 호출한 결과를 인수별로 저장해 두는 기법입니다. 같은 인수로 다시 호출하면 새로 계산하지 않고 저장해 둔 결과를 돌려줍니다.
핵심 포인트
if number < 2: return number는 처음 두 항인 0과 1을 돌려줍니다.fibonacci(number - 1) + fibonacci(number - 2)는 피보나치 수열의 정의를 그대로 옮긴 것입니다.functools의@cache가 결과를 모두 기억하므로, 각fibonacci(k)는 한 번만 실행됩니다.@cache가 없으면fibonacci(10)은 함수를 177번 호출하지만, 있으면 11번만 호출합니다.
언제 사용하나요?
- 같은 하위 문제를 되풀이해서 푸는 재귀 함수: 격자에서 경로 세기, 거스름돈 만들기, 단어 나누기.
- 동적 계획법의 바탕이 되는 아이디어를 배울 때.
- 같은 인수로 자주 호출되는 순수 함수의 속도를 높일 때.
필요 없는 경우
- 부수 효과가 있거나 결과가 시간에 따라 달라지는 함수: 캐시가 오래된 답을 돌려주게 됩니다.
- 아주 깊은 재귀: 캐시가 있어도
fib(5000)은 재귀 한도를 넘을 수 있습니다. 반복문으로 쓰면 이 문제가 없습니다.
동작 원리 보기
한 단계를 눌러 각 호출을 따라가세요. fib가 같은 작은 값들을 계속 다시 계산하는 것에 주목하세요. 단순한 버전이 느린 이유입니다.
예제 코드
from functools import cache
@cache
def fibonacci(number):
if number < 2:
return number
return fibonacci(number - 1) + fibonacci(number - 2)
print(fibonacci(10))
실행 결과
55
코드 설명
@cache 데코레이터는 각 입력값에 대한 함수 결과를 자동으로 저장합니다. fibonacci(8)을 한 번 계산하면 이후 호출은 결과를 바로 가져옵니다. 그래서 실행 시간이 지수 시간에서 O(n)으로 줄어들고, 대신 결과를 저장하는 데 O(n) 메모리를 씁니다.
값을 변경하고 Python 설치 없이 CodeUtility 온라인 Python 컴파일러에서 실행하세요.
연습 문제
아래 제안을 따라 코드를 바꿔 보세요. 코드를 직접 고치고 결과를 확인하면 읽기만 할 때보다 레슨을 훨씬 잘 이해할 수 있습니다.
- 빈 리스트, 요소가 하나인 리스트, 중복이 있는 리스트로 테스트해 보세요.
- 단계마다 상태를 출력해서 알고리즘이 동작하는 모습을 살펴보세요.
- 요소 100개, 1,000개, 10,000개로 실행 시간을 재고 다른 방법과 비교해 보세요.
자주 하는 실수
캐시 없이 재귀하기
같은 값을 몇 번이고 다시 계산해서 fib(40)에 몇 초씩이나 걸립니다.
def fibonacci(number):
if number < 2:
return number
return fibonacci(number - 1) + fibonacci(number - 2)
@cache
def fibonacci(number):
if number < 2:
return number
return fibonacci(number - 1) + fibonacci(number - 2)
이 레슨을 마쳤나요?
학습 완료로 표시하면 진행 상황을 기록할 수 있습니다.
챌린지로 연습하기
이 레슨에서 배운 내용으로 실제 문제를 풀어 보세요. 모든 챌린지는 브라우저에서 실행되며 즉시 테스트와 AI 리뷰를 받을 수 있습니다.
모든 챌린지