---
title: "메모이제이션: 같은 질문의 답을 한 번만 계산하기"
author: "Lee"
published_at: "2026-10-17T04:36:03.492Z"
updated_at: "2026-09-30T09:49:31.637Z"
tags: ["컴퓨터공학","알고리즘"]
canonical_url: "https://ariser.io/@writer_a1cd615ab19e/%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98-%EA%B0%99%EC%9D%80-%EC%A7%88%EB%AC%B8%EC%9D%98-%EB%8B%B5%EC%9D%84-%ED%95%9C-%EB%B2%88%EB%A7%8C-%EA%B3%84%EC%82%B0%ED%95%98%EA%B8%B0"
ai_assisted: false
---

# 메모이제이션: 같은 질문의 답을 한 번만 계산하기

[원문](https://ariser.io/@writer_a1cd615ab19e/%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98-%EA%B0%99%EC%9D%80-%EC%A7%88%EB%AC%B8%EC%9D%98-%EB%8B%B5%EC%9D%84-%ED%95%9C-%EB%B2%88%EB%A7%8C-%EA%B3%84%EC%82%B0%ED%95%98%EA%B8%B0)

메모이제이션은 함수가 이미 계산한 결과를 인자나 상태를 키로 저장하고, 같은 질문이 다시 오면 재사용하는 기법이다. 재귀로 문제를 표현하기 쉽지만 같은 부분문제가 반복될 때 효과가 크다. 단순히 모든 결과를 무작정 저장하는 것과는 다르다.

![F4 계산에서 F2 등 같은 하위 문제를 한 번 계산해 다시 이용하는 메모이제이션](/api/v1/media/02ffa757-c75d-44c5-b0a9-cf80e9be2574)

*같은 상태로 다시 요청된 계산은 저장된 결과를 이용한다.*

### 피보나치에서 중복이 생기는 구조

F(n)=F(n-1)+F(n-2)를 그대로 구현하면 F(5)를 구하는 여러 갈래에서 F(3),F(2)를 다시 계산한다. 캐시가 있으면 각 인자에 대한 계산은 한 번만 수행하고 이후 호출은 저장된 값을 읽는다.

```python
def make_fibonacci():
    cached_answers = {0: 0, 1: 1}
    def fibonacci(index):
        if index < 0:
            raise ValueError("Index must be nonnegative")
        if index in cached_answers:
            return cached_answers[index]
        computed = fibonacci(index - 1) + fibonacci(index - 2)
        cached_answers[index] = computed
        return computed
    return fibonacci

fibonacci = make_fibonacci()
answer = fibonacci(10)
```

이 코드는 캐시를 함수 내부 환경에 보관한다. 답이 0일 수도 있으므로 “값이 참인가”가 아니라 키가 있는지 검사한다. 먼저 캐시 존재를 확인하지 않으면 계산을 끝낸 뒤 저장하더라도 반복 호출에서 재사용하지 못한다.

### 상태 키가 완전해야 한다

배낭 함수의 답이 물건 인덱스와 남은 용량에 모두 의존한다면 캐시 키에도 둘 다 있어야 한다. 남은 용량만 저장하면 서로 다른 물건 집합의 답을 섞는다. 전역 설정, 현재 시간, 외부 DB가 결과에 영향을 주는 함수는 인자만 같은 것으로 충분하지 않을 수 있다.

입력과 같은 환경에서 결과가 일정한 순수 함수는 캐싱하기 쉽다. 부수 효과가 있는 함수를 캐시하면 두 번째 실행의 효과가 생략될 수 있다. 파일 쓰기나 결제 같은 작업을 수치 계산처럼 저장해서는 안 된다.

피보나치의 서로 다른 상태는 n+1개이고 상태당 덧셈을 일정 비용으로 보면 시간 O(n), 캐시와 호출 스택 공간은 O(n)이다. 큰 정수는 자리 수가 늘어 덧셈 자체도 더 비싸므로 정확한 비트 복잡도는 별도다.

Top-down 메모이제이션은 실제 요청된 상태만 계산한다. Bottom-up 표 채우기는 의존 순서를 명시하고 재귀 스택을 없앨 수 있다. 같은 상태 전이를 표현하더라도 도달 상태의 수, 호출 비용, 메모리 재사용 가능성에 따라 장단점이 달라진다.

캐시는 메모리를 점유하고 오래된 결과를 유지할 수 있다. 상태 수가 너무 크면 제한된 캐시나 다른 알고리즘이 필요하다. 여러 스레드가 동시에 같은 상태를 계산하면 중복 실행이나 공유 상태 문제가 생길 수도 있다. 결과의 재사용이 정확한 조건과 캐시의 수명을 함께 정의해야 한다.

### 참고 자료

- [MIT OpenCourseWare · Introduction to Algorithms](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/)