메모이제이션 (Memoization)

도입

메모이제이션은 이미 계산한 결과를 저장해 두고 다시 같은 계산이 필요할 때 재사용함으로써 중복 연산을 제거하는 핵심 최적화 기법이다

메모이제이션(Memoization)은 재귀나 동적 계획법 문제에서 매우 자주 등장하는 최적화 기법입니다. 어떤 함수가 같은 입력에 대해 같은 결과를 반환한다면, 한 번 계산한 결과를 저장해 두었다가 다음에 같은 입력이 들어왔을 때 다시 계산하지 않고 곧바로 꺼내 쓰는 방식입니다.

즉, 메모이제이션의 핵심은 중복 계산을 줄이는 것입니다. 단순 재귀는 구조는 아름답지만 같은 하위 문제를 여러 번 반복해서 풀기 쉽습니다. 이때 메모이제이션을 적용하면 재귀의 장점은 유지하면서 시간 복잡도를 크게 줄일 수 있습니다.

필요성

메모이제이션을 이해하면 지수 시간 재귀를 선형 또는 다항 시간으로 줄일 수 있는 이유가 명확해지고, 재귀와 DP의 연결 구조가 선명해진다

재귀 문제를 풀다 보면 코드는 짧고 자연스러운데 시간 초과가 나는 경우가 많습니다. 그 대표적인 이유가 바로 같은 하위 문제를 계속 다시 푸는 구조입니다. 메모이제이션은 이 중복을 제거해, 원래 문제의 논리를 유지하면서도 성능을 크게 개선할 수 있게 해 줍니다.

메모이제이션이 특히 중요한 상황

• 같은 입력을 여러 번 계산하는 재귀
• 피보나치 같은 점화식 문제
• 최대값 / 최소값을 구하는 DP 문제
• 경우의 수, 조합 수, 경로 수 계산
• 문자열 DP, 배낭 문제, 게임 DP
• 탐색 과정에서 상태가 반복되는 문제

정의

메모이제이션은 함수 호출 결과를 저장해 두고 동일한 상태나 입력이 다시 등장했을 때 저장된 결과를 즉시 반환하는 캐싱 기법이다

메모이제이션은 이름 그대로 “기억해 두기” 전략입니다. 어떤 문제를 풀 때 특정 입력 상태의 답을 한 번 계산했다면, 그 결과를 배열이나 Map에 저장해 둡니다. 이후 같은 입력이 다시 나오면 재귀를 더 내려가지 않고 저장된 값을 반환합니다.

구성 요소	의미	예시
상태(State)	문제를 구분하는 입력 정보	n, (i,j), (idx,sum)
저장소(Cache)	이미 계산한 결과를 보관하는 공간	배열, HashMap
재사용	같은 상태가 다시 나오면 저장값 반환	if (memo[n] != -1) return memo[n];

왜 빨라지는가

메모이제이션이 성능을 높이는 이유는 새로운 문제를 더 빨리 푸는 것이 아니라, 이미 푼 문제를 다시 풀지 않게 만들기 때문이다

메모이제이션의 핵심은 계산 그 자체를 최적화하는 것이 아니라 계산 횟수를 줄이는 데 있습니다. 같은 상태가 여러 경로에서 다시 등장하는 문제라면, 처음 한 번만 계산하고 나머지는 저장된 값을 쓰면 됩니다.

중복 계산이 많은 재귀
→ 같은 상태를 여러 번 방문
→ 메모이제이션으로 한 번만 계산
→ 나머지는 즉시 반환

즉, 메모이제이션은 “새로운 계산을 빠르게 한다”보다 “불필요한 계산 자체를 없앤다”고 이해하는 것이 정확합니다.

재귀와의 관계

메모이제이션은 재귀를 대체하는 기법이 아니라, 재귀가 가진 중복 호출 문제를 보완해 주는 가장 대표적인 확장 방식이다

메모이제이션은 재귀와 아주 자주 함께 등장합니다. 보통 먼저 재귀식으로 문제를 정의하고, 그 재귀에서 같은 상태가 반복되는 것을 확인한 뒤 저장소를 붙여 최적화합니다. 그래서 메모이제이션은 흔히 Top-Down DP와 거의 같은 문맥으로 설명됩니다.

재귀 + 메모이제이션 흐름

• 문제를 재귀적으로 정의한다.
• 종료 조건을 만든다.
• 상태를 식별할 수 있게 정한다.
• 저장소를 만든다.
• 계산 전에 저장된 값이 있는지 확인한다.
• 없으면 계산하고 저장한 뒤 반환한다.

가장 기본 예시

피보나치 수열은 메모이제이션이 왜 필요한지를 가장 직관적으로 보여 주는 대표 예시다

단순 재귀 피보나치는 같은 값을 끝없이 다시 계산합니다. 하지만 한 번 구한 값을 배열에 저장하면 각 n은 한 번만 계산하면 됩니다.

static int[] memo = new int[100];

static int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];

    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

이 예시는 메모이제이션의 핵심을 그대로 보여 줍니다. 계산 전에 저장 여부를 확인하고, 없으면 계산 후 저장한다는 패턴입니다.

배열과 Map 중 무엇을 쓰나

메모이제이션 저장소는 상태 표현 방식에 따라 배열이 더 적합할 수도 있고, Map이 더 적합할 수도 있다

저장소	언제 적합한가	예시
배열	상태가 정수 인덱스로 깔끔하게 표현될 때	fib(n), dp[i], dp[i][j]
HashMap	상태가 희소하거나 문자열/튜플 형태일 때	(x,y), (idx,sum), 문자열 상태

배열은 빠르고 단순하지만, 상태 범위가 크거나 음수·문자열·복합 상태를 포함하면 비효율적일 수 있습니다. 이런 경우에는 HashMap 기반 메모이제이션이 더 유연합니다.

static Map<String, Integer> memo = new HashMap<>();

static int solve(int x, int y) {
    String key = x + "," + y;
    if (memo.containsKey(key)) return memo.get(key);

    int result = x + y; // 예시
    memo.put(key, result);
    return result;
}

패턴 1. Top-Down DP

메모이제이션은 동적 계획법을 재귀적으로 구현하는 Top-Down 방식의 핵심 구성 요소다

동적 계획법은 보통 중복되는 부분 문제와 최적 부분 구조를 가지는 문제에서 쓰입니다. 이때 Bottom-Up이 반복문 기반이라면, Top-Down은 재귀 + 메모이제이션 기반입니다.

static int[] dp = new int[1001];
static boolean[] visited = new boolean[1001];

static int solve(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (visited[n]) return dp[n];

    visited[n] = true;
    dp[n] = solve(n - 1) + solve(n - 2);
    return dp[n];
}

여기서는 값이 0일 수도 있기 때문에 단순히 dp[n] != 0로 확인하지 않고, 별도의 visited 배열을 두는 방식이 더 안전합니다.

패턴 2. 탐색 상태 캐싱

재귀 탐색에서 같은 상태를 여러 경로로 다시 방문한다면, 메모이제이션은 단순 DP를 넘어 탐색 자체를 줄이는 도구가 된다

DFS나 게임 탐색, 문자열 문제에서는 단순 숫자 하나가 아니라 여러 변수 조합이 상태가 됩니다. 이때 상태를 키로 만들어 저장하면, 같은 상태에 대한 하위 탐색을 반복하지 않아도 됩니다.

static Map<String, Integer> memo = new HashMap<>();

static int dfs(int idx, int sum) {
    String key = idx + ":" + sum;
    if (memo.containsKey(key)) return memo.get(key);

    if (idx == n) return sum == target ? 1 : 0;

    int result = dfs(idx + 1, sum + nums[idx]) +
                 dfs(idx + 1, sum - nums[idx]);

    memo.put(key, result);
    return result;
}

이 방식은 단순 계산을 저장하는 수준을 넘어, 탐색 공간 자체를 줄이는 역할을 합니다.

시간 복잡도 변화

메모이제이션의 성능 향상은 보통 “호출 수를 상태 수 수준으로 줄인다”는 방식으로 이해하면 가장 명확하다

예를 들어 피보나치의 단순 재귀는 거의 같은 값을 계속 다시 계산하므로 호출 수가 폭발적으로 늘어납니다. 하지만 메모이제이션을 쓰면 각 n 값은 한 번만 계산하면 되므로, 전체 호출 수는 사실상 상태 수와 비슷해집니다.

방식	상태 재계산	시간 복잡도 감각
단순 재귀	매우 많음	지수적으로 커질 수 있음
메모이제이션 적용	같은 상태는 한 번만 계산	대개 상태 수 × 전이 비용 수준

언제 안 통하는가

메모이제이션은 모든 재귀를 빠르게 만드는 마법이 아니며, 같은 상태가 반복되지 않거나 상태 수가 너무 크면 효과가 작을 수 있다

메모이제이션이 잘 작동하려면 중복되는 부분 문제가 실제로 존재해야 합니다. 상태가 매번 완전히 달라서 재방문이 거의 없다면 저장의 이점이 거의 없습니다. 또한 상태 수가 지나치게 많으면 저장 공간이 부담이 될 수 있습니다.

효과가 제한적일 수 있는 경우

• 상태가 거의 중복되지 않는 탐색
• 상태 표현이 너무 커서 저장이 비싼 문제
• 반복문 기반 Bottom-Up이 더 단순한 문제
• 스택 깊이가 너무 깊어 재귀 자체가 위험한 문제

자주 하는 실수

메모이제이션이 틀리는 이유는 대개 상태 정의 오류, 저장 여부 판별 실수, 캐시 초기화 누락, 불완전한 키 설계 때문이다

• 상태를 구분하는 변수를 일부 빼먹어 다른 문제를 같은 것으로 취급함
• 값이 0일 수도 있는데 0을 미계산 표시로 써서 오답이 남
• 테스트 케이스마다 memo 초기화를 하지 않아 이전 결과가 섞임
• Map 키를 모호하게 만들어 서로 다른 상태가 같은 키가 됨
• 종료 조건보다 memo 조회 순서를 잘못 배치해 예외가 남
• 중복 상태가 없는 문제인데 무조건 메모이제이션부터 붙여 메모리만 낭비함

풀이 루틴

메모이제이션 문제를 풀 때는 코드보다 먼저 “상태가 무엇인지”와 “같은 상태가 다시 나타나는지”부터 확인하는 습관이 중요하다

1. 재귀 함수의 의미를 먼저 문장으로 정의한다.
2. 종료 조건을 가장 먼저 정한다.
3. 상태를 구분하는 변수가 무엇인지 정한다.
4. 상태 범위가 작으면 배열, 복잡하면 Map을 선택한다.
5. 함수 시작 부분에서 이미 계산한 상태인지 먼저 확인한다.
6. 없으면 계산하고 반드시 저장한 뒤 반환한다.
7. 상태 수가 너무 크면 Bottom-Up이나 다른 접근이 더 나은지도 본다.

디버깅

메모이제이션이 꼬일 때는 재귀 로직보다도 상태 정의와 캐시 조회·저장 타이밍을 먼저 점검해야 한다

1

같은 상태를 구분하는 정보가 빠지지 않았는지 확인한다.

2

memo 조회가 종료 조건보다 앞서야 하는지, 뒤여야 하는지 순서를 점검한다.

3

0이나 false가 실제 답이 될 수 있다면 미계산 표시를 따로 두는지 확인한다.

4

계산한 값을 반환만 하고 저장하지 않았는지 확인한다.

5

테스트 케이스가 여러 개라면 캐시를 매번 초기화하는지 본다.

요약

메모이제이션은 이미 계산한 상태의 결과를 저장하고 재사용해 중복 계산을 제거하는 기법이며, 재귀와 DP를 연결하는 가장 중요한 최적화 도구 중 하나다

• ✅ 메모이제이션은 같은 상태의 계산 결과를 저장해 중복 호출을 없애는 기법이다.
• ✅ 재귀와 함께 쓰이면 단순 재귀의 시간 초과를 크게 줄일 수 있다.
• ✅ 핵심은 함수가 아니라 상태를 저장하는 것이며, 상태 정의가 가장 중요하다.
• ✅ 상태 범위가 작으면 배열, 복잡하거나 희소하면 Map이 자주 쓰인다.
• ✅ 메모이제이션은 Top-Down DP의 핵심이며, 상태 수만큼만 계산하도록 만드는 것이 목표다.
• ✅ 중복 상태가 거의 없는 문제나 상태 수가 너무 큰 문제에서는 효과가 제한적일 수 있다.