메모이제이션 (Memoization)

메모이제이션 (Memoization)

이미 계산한 결과를 저장(캐싱)하여 동일한 계산이 반복될 때 저장된 값을 반환함으로써 중복 계산을 방지하는 최적화 기법

목적: 중복 계산 제거, 지수 시간→다항 시간 개선, 동적 프로그래밍 구현

특징: 캐싱, Top-Down 방식, 재귀와 결합, 시간-공간 트레이드오프

구현 방법

피보나치 예시

• •순수 재귀: O(2^n) - 중복 계산 폭발
• •메모이제이션: O(n) - 각 fib(i)는 한 번만 계산

Top-Down vs Bottom-Up

• •Top-Down (메모이제이션): 재귀 + 캐싱, 필요한 것만 계산
• •Bottom-Up (테이블): 반복문, 작은 문제부터 순차 계산

장점: 중복 계산 제거, 지수→다항 시간, 코드 변경 최소

단점: 메모리 사용 증가, 재귀 오버헤드, 스택 오버플로우 가능

적용사례: 피보나치, LCS, 편집 거리, 배낭 문제, 경로 문제

비교: 메모이제이션(Top-Down/재귀) vs 테이블(Bottom-Up/반복)

연관: 동적 프로그래밍, 재귀, 캐싱, 시간 복잡도 최적화