메모이제이션 (Memoization)
쉽게 풀면
어려운 수학 문제를 풀 때마다 풀이 과정을 노트에 적어두었다가, 나중에 똑같은 문제가 다시 나오면 처음부터 다시 풀지 않고 노트를 펼쳐 답만 옮겨 적는 것과 같습니다. 재귀 함수는 같은 부분 문제를 여러 번 반복해서 계산하는 경우가 많은데, 한 번 계산한 결과를 캐시(임시 저장소)에 담아두면 다음번엔 그 값을 그대로 재사용할 수 있어 전체 계산량이 크게 줄어듭니다.
왜 중요한가
메모이제이션은 알고리즘의 시간 복잡도를 지수적 수준에서 다항 시간 수준으로 낮출 수 있는 핵심 최적화 기법이기 때문에 알고리즘, 컴파일러, 시스템 성능 연구 전반에서 자주 언급됩니다. 특히 같은 계산이 반복되는 재귀 구조를 가진 문제(동적 계획법으로 풀리는 문제들)에서는 메모이제이션 적용 여부가 실행 가능성 자체를 좌우하기도 하며, 웹 서버의 캐싱 전략이나 대규모 언어 모델의 추론 가속화처럼 실무 시스템 설계에서도 같은 원리가 폭넓게 응용됩니다.
논문에서는 이렇게 쓰입니다
이 문장은 원래 지수 시간이 걸리던 재귀 알고리즘이, 이미 계산한 부분 문제의 답을 저장해두는 방식을 도입함으로써 선형 시간까지 빨라졌다는 성능 개선 결과를 설명하고 있습니다.
이 문장은 입력이 같으면 항상 같은 결과를 내는 함수의 성질을 이용해, 개발자가 직접 캐시를 구현하지 않아도 컴파일러가 알아서 결과를 저장하고 재사용하도록 만드는 최적화 방법을 소개했다는 뜻입니다.
이 문장은 문장을 한 단어씩 생성하는 언어 모델이 매번 이전 계산을 반복하지 않도록, 중간 계산 결과를 저장해두고 재사용함으로써 생성 속도를 높였다는 뜻입니다.
조금 더 깊게 보면
메모이제이션이 제대로 동작하려면 함수가 같은 입력에 대해 항상 같은 출력을 내는 순수 함수(pure function) 성질을 가져야 하며, 이 조건이 깨지면 캐시된 값이 틀린 결과를 반환할 위험이 있습니다. 캐시를 저장하는 자료구조로는 보통 해시테이블이 쓰이는데, 입력 조합이 매우 많아지면 캐시 자체가 차지하는 메모리가 커지는 공간-시간 트레이드오프가 발생합니다. 이런 이유로 캐시 크기를 제한하고 오래된 항목을 지우는 LRU(least recently used) 같은 캐시 교체 전략을 함께 적용하는 경우도 흔합니다.
주의할 점
메모이제이션은 재귀 함수 위에 캐시를 얹는 '하향식(top-down)' 접근이라는 점에서, 작은 문제부터 차례로 표를 채워나가는 '상향식(bottom-up)' 방식인 동적계획법과 구분됩니다. 둘 다 같은 부분 문제를 반복 계산하지 않는다는 원리는 같지만, 구현 방향이 반대라는 점을 혼동하지 않아야 합니다.