Memoization Explanation - JavaScript.ac

Problem Summary

Write a memoize function that caches the results of expensive function calls.

Detailed Explanation

이 문제는 **메모이제이션** 패턴을 학습합니다. 같은 입력에 대한 반복 계산을 피해 성능을 최적화합니다. **메모이제이션이란?** 함수 호출 결과를 캐싱하여, 같은 인수로 다시 호출될 때 저장된 결과를 반환하는 기법입니다. **동작 원리** 1. 인수를 키로 변환 (JSON.stringify) 2. 캐시에 키가 있으면 저장된 결과 반환 3. 없으면 함수 실행 후 결과 저장 **캐시 키 생성** `JSON.stringify(args)`로 인수 배열을 문자열로 변환: - memoizedFn(1, 2) → 키: "[1,2]" - memoizedFn(1, 2) 다시 호출 → 캐시 히트! **피보나치 예시** ```javascript const fib = memoize(n => { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); }); ``` 메모이제이션 없이 fib(40)은 매우 느리지만, 메모이제이션으로 즉시 계산됩니다. **클로저의 역할** 반환된 함수는 cache 객체에 접근할 수 있습니다. 각 메모이즈된 함수는 자신만의 캐시를 가집니다. **fn.apply(this, args)** 원본 함수를 올바른 컨텍스트(this)와 인수로 호출합니다.

Solution Code

solution.js

function memoize(fn) {
  const cache = {};
  return function(...args) {
    const key = JSON.stringify(args);
    if (key in cache) return cache[key];
    const result = fn.apply(this, args);
    cache[key] = result;
    return result;
  };
}

Key Concepts from This Problem

1. 메모이제이션 패턴

2. 캐싱

3. 클로저

4. 성능 최적화

Common Mistakes

✗ 객체나 배열 인수는 JSON.stringify로 변환해야 올바른 키가 됩니다

✗ 부작용이 있는 함수는 메모이제이션하면 안 됩니다

✗ 캐시가 무한히 커질 수 있으므로 크기 제한이 필요할 수 있습니다

Hints

Hint 1: 객체로 캐시를 만드세요.

Hint 2: JSON.stringify로 키를 만드세요.

Complexity Analysis

Time Complexity

O(1) 캐시 히트, O(f(n)) 미스

Space Complexity

O(n)

Uses memory proportional to input size

Related Tags

#함수 #캐시 #최적화