메모이제이션 (memoization) - 알고리즘 최적화

메모이제이션

메모이제이션은 같은 입력으로 이미 계산/조회 한 결과를 기억해 두었다가, 다시 필요할 때 반복하지 않고 기억한 내용을 재사용하는 기법이다. 즉, 함수의 중복 호출을 방지해 효율을 높여준다. 

 

알고리즘에 추가하는 성능 개선 패턴, 최적화 기법에 가깝다. 주로 DFS + 메모이제이션, DP의 top-down 방식(=메모이제이션)

 

 

왜 쓰는가?

시간 복잡도 관점에서, 중복 조회가 많을 경우 유의미하게 조회 횟수를 줄일 수 있다. 공간을 사용해서 시간을 아끼는 것.

 

 

캐시와의 차이

메모이제이션 : 보통 짧은 범위 (한 메서드, 한 요청)

캐시 : TTL, 크기 제한, 서버 간 공유까지 고려

 

 

어떻게 쓰는가

Map<K, V> memo = new HashMap<>();
memo.computeIfAbsent(key, k -> expensiveWork(k));

 

computeIfAbsent 는 map 에서 key 가 있으면 기존 값 반환, 없으면 함수 실행값을 반환하는 메서드이다. 사용 시 재귀호출 주의가 필요하다.

항상 메모이제이션 = HashMap 은 아니다.

 

 

주의사항

메모이제이션은 같은 입력에 항상 같은 출력이라는 전제가 있어야 한다. 내부 상태나 외부 값에 따라 결과가 달라지는 함수는 메모이제이션 하면 안된다.