2025-08-27 01:03
메모이제이션
- 한번 계산한건 다시 계산하지 말자!
- 함수 호출 결과를 저장해 뒀다가 동일한 입력에 대해 재사용해서 속도 높이는 최적화 기법
- 계산 비용 높고, 동일한 입력 반복되는 순수 함수에 적용할때 가장 효과적 (Like 피보나치 수열)
- 시간 복잡도를 낮추기 위해 공간 복잡도를 희생하는 방식
- 캐싱 구조를 사용해 특정 입력값 들어오면 먼저 캐시 확인하고 있으면 가져다 쓰는 방식으로 구현
- 보통 동적 계획법 에서 타뷸레이션 과 비교되며 사용
메모이제이션을 사용하기 좋은 경우
| 조건 | 설명 | 예시 |
|---|---|---|
| 순수 함수 (Pure Functions) | 동일한 입력에 대해 항상 동일한 출력을 반환하고, 외부 상태를 변경하지 않는(side effect가 없는) 함수여야 합니다. | 수학 계산 함수, 데이터 변환 함수 |
| 높은 계산 비용 | 함수의 실행 시간이 길거나 계산 과정이 복잡하여 최적화의 가치가 있어야 합니다. | 복잡한 재귀 함수, 대규모 데이터 처리 |
| 반복되는 입력값 | 동일한 입력값으로 함수가 자주 호출되어야 캐시 히트의 이점을 누릴 수 있습니다. | 이벤트 핸들러, 렌더링 로직 |