메모이제이션
메모이제이션은 함수나 부분 문제의 계산 결과를 키와 함께 저장하고 동일한 요청에 재사용하는 방법이다. 알고리즘의 동적 계획법 구현 기법 분야에서 다루며, 문제를 어떤 하위 단계로 표현하고 어떤 계산을 생략하거나 공유할지를 결정하는 방법이다. 이 기법을 적용할 때에는 결과의 정확성뿐 아니...
| 분류 | 알고리즘 · 동적 계획법 구현 기법 |
|---|---|
| 목적 | 함수나 부분 문제의 계산 결과를 키와 함께 저장하고 동일한 요청에 재사용하는 방법 |
| 핵심 과정 | 재귀 함수 호출 시 인수·상태를 캐시에서 조회하고 없으면 계산해 저장한다 |
| 시간·연산 비용 | 최초 계산된 서로 다른 상태 수 × 전이 비용; 캐시 크기는 방문한 상태 수 |
| 적용 전제 | 동일한 입력 상태가 동일한 결과를 내는 성질이 필요하며 캐시 키가 상태를 충분히 표현해야 한다 |
| 관련 분야 | 알고리즘 설계, 계산 복잡도 |
| 참고 자료 | MIT 알고리즘 강의 |
메모이제이션은 함수나 부분 문제의 계산 결과를 키와 함께 저장하고 동일한 요청에 재사용하는 방법이다. 알고리즘의 동적 계획법 구현 기법 분야에서 다루며, 문제를 어떤 하위 단계로 표현하고 어떤 계산을 생략하거나 공유할지를 결정하는 방법이다. 이 기법을 적용할 때에는 결과의 정확성뿐 아니라 종료 조건, 필요한 상태의 표현과 입력 조건을 함께 정의한다.[1]
핵심 처리 과정은 다음과 같다. 재귀 함수 호출 시 인수·상태를 캐시에서 조회하고 없으면 계산해 저장한다. 상태 그래프의 필요한 부분만 방문하므로 모든 가능한 상태를 미리 계산할 필요가 없다. 설계 시에는 각 단계에서 보존되어야 할 불변식이나 조건을 정의하고, 결과를 반환하기까지 어떤 상태가 수정되는지를 추적한다.
계산 자원은 문제의 크기와 구현 방식에 좌우된다. 최초 계산된 서로 다른 상태 수 × 전이 비용; 캐시 크기는 방문한 상태 수. 적용 조건은 동일한 입력 상태가 동일한 결과를 내는 성질이 필요하며 캐시 키가 상태를 충분히 표현해야 한다라는 점이다. 이 조건이 성립하는지를 먼저 확인해야 동일한 절차를 다른 입력에도 일관되게 사용할 수 있다.
피보나치 계산, 그래프의 상태 탐색, 파싱과 동적 계획법 구현에 사용된다. 캐시의 무제한 증가, 순환 상태와 부수 효과에 따른 정합성을 고려한다. 실제 구현에서는 상태 표현, 자료구조 선택, 재귀 호출 또는 반복 처리, 메모리 접근과 경계 입력을 함께 고려한다. 이론적 계산 모델과 구체적인 프로그램의 시간·공간 비용은 입력 분포와 실행 환경에 따라 달라질 수 있다.[2]