재귀와 메모이제이션 Fibonacci
메모이제이션은 이전 함수 결과를 캐시에 저장합니다.
재귀와 메모이제이션 Fibonacci이란?
메모이제이션은 이전 함수 결과를 캐시에 저장합니다.
같은 Fibonacci 값을 다시 계산하지 않습니다.
언제 사용하나요?
- 알고리즘과 자료 구조를 이해합니다.
- 각 단계와 경계 조건을 확인합니다.
- 실행 시간과 메모리 사용량을 비교합니다.
예제 코드
main.py
from functools import cache
@cache
def fibonacci(number):
if number < 2:
return number
return fibonacci(number - 1) + fibonacci(number - 2)
print(fibonacci(10))예상 출력
55작동 원리
순진한 지수 시간을 O(n)으로 줄이고 O(n) 메모리를 사용합니다.
값을 변경하고 Python 설치 없이 CodeUtility 온라인 Python 컴파일러에서 실행하세요.
연습 문제
입력값과 경계 조건을 바꾸고 더 큰 데이터에서도 동작을 확인하세요.
- 빈 입력, 한 요소, 중복값을 시험하세요.
- 각 단계의 상태를 출력하세요.
- 다른 풀이와 성능을 비교하세요.