[코딩테스트] 메모이제이션

메모이제이션은 DP(동적 프로그래밍)의 구현 기법 중 하나다. 개념 자체는 단순한데, 처음 들으면 이름이 낯설어서 어렵게 느껴진다.

핵심 아이디어

같은 계산을 두 번 하지 않는다.

함수를 호출했을 때 그 결과를 어딘가에 저장해두고, 나중에 같은 입력으로 다시 호출되면 저장된 값을 그대로 반환한다. 연산을 건너뛰는 것이다.

f(5) 호출 → 계산 후 결과를 memo[5]에 저장
f(5) 재호출 → memo[5]에 값이 있으므로 계산 없이 바로 반환

이게 전부다. 저장(memo) + 재사용이 메모이제이션의 본질이다.

피보나치로 보는 차이

메모이제이션이 왜 필요한지는 피보나치 수열로 가장 잘 설명된다.

f(n) = f(n-1) + f(n-2)를 단순 재귀로 구현하면 이런 일이 벌어진다.

f(3)이 2번, f(2)가 3번 계산된다. n이 커질수록 중복 계산이 기하급수적으로 늘어나 O(2ⁿ)이 된다.

메모이제이션을 적용하면 각 f(n)을 딱 한 번만 계산한다. 시간복잡도가 O(2ⁿ) → O(n)으로 줄어든다.

구현

Java 기준으로 두 가지 방식이 있다.

배열로 메모

int[] memo = new int[n + 1];
Arrays.fill(memo, -1);  // -1 = 아직 계산 안 됨

int f(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];  // 이미 계산했으면 반환
    return memo[n] = f(n - 1) + f(n - 2);  // 계산 후 저장
}

• memo[n] != -1 체크가 핵심이다. 저장된 값이 있으면 바로 반환한다.
• 초기값을 -1로 채우는 이유는 0이 유효한 결과일 수 있기 때문이다.

HashMap으로 메모

입력이 정수 범위를 벗어나거나 희소할 때 사용한다.

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

int f(int n) {
    if (n <= 1) return n;
    if (memo.containsKey(n)) return memo.get(n);
    int result = f(n - 1) + f(n - 2);
    memo.put(n, result);
    return result;
}

배열로 관리할 수 있다면 배열이 더 빠르다. HashMap은 해싱 비용이 있다.

메모이제이션 vs 카운터 배열

메모이제이션과 헷갈리기 쉬운 것이 카운터 배열이다 (예: 슬라이딩 윈도우의 freq[]).

	메모이제이션	카운터 배열 (freq[])
목적	재계산 방지	현재 상태 추적
값의 의미	"이 입력에 대한 답은 X"	"이 항목이 현재 X개 있음"
갱신 시점	한 번 계산하면 고정	매 이동마다 ++/--
사용 알고리즘	DP, 재귀 최적화	슬라이딩 윈도우, 빈도 집계

둘 다 배열에 값을 저장한다는 점은 같지만, 용도가 다르다. 메모이제이션은 "이미 계산했냐"를 체크하기 위한 것이고, 카운터 배열은 "지금 몇 개냐"를 실시간으로 관리하기 위한 것이다.

언제 메모이제이션을 쓰는가

재귀 함수에서 같은 인자로 호출되는 경우가 반복될 때 적용한다. 판단 기준은 두 가지다.

1. 부분 문제가 겹치는가 (overlapping subproblems)
2. 같은 입력에 대해 항상 같은 결과가 나오는가 (referential transparency)

둘 다 해당하면 메모이제이션을 쓸 수 있다. 대표적인 문제 유형으로는 피보나치, 최장 공통 부분수열(LCS), 배낭 문제, 동전 거스름돈 등이 있다.

---