메모이제이션 (Memoization)

메모이제이션은 “기억하다"라는 뜻의 라틴어 ‘memorandum’에서 유래했다.
이 기법은 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장해두고 필요할 때 다시 계산하지 않고 저장된 값을 사용하는 방식이다.

실생활에 비유해보면, 책을 보다가 모르는 단어를 사전에서 찾았을 때

  1. 메모이제이션 미사용: 같은 단어가 나올 때마다 매번 사전을 찾음
  2. 메모이제이션 사용: 찾은 단어의 의미를 메모장에 적어두고, 다시 나오면 메모장을 참고
    로 이해 가능하다.

메모이제이션의 작동 원리

  1. 함수가 호출될 때 입력값을 확인한다.
  2. 해당 입력값에 대한 결과가 이미 저장되어 있다면, 저장된 결과를 즉시 반환한다.
  3. 저장된 결과가 없다면, 함수를 실행하고 그 결과를 저장한 후 반환한다.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def memoized_function(n, memo={}):
    # 1. 이미 계산된 값인지 확인
    if n in memo:
        return memo[n]
        
    # 2. 새로운 값 계산
    result = ... # 계산 로직
    
    # 3. 계산된 값을 저장
    memo[n] = result
    
    # 4. 결과 반환
    return result

메모이제이션의 장점

  1. 실행 속도 향상: 중복 계산을 피함으로써 프로그램의 실행 속도를 크게 높일 수 있다.
  2. 자원 효율성: 계산 비용이 높은 작업의 결과를 재사용함으로써 컴퓨터 자원을 효율적으로 사용할 수 있다.

메모이제이션의 사용 예시

가장 대표적인 예시로 피보나치 수열 계산을 들 수 있다.
일반적인 재귀 함수로 구현하면 중복 계산이 많이 발생하지만, 메모이제이션을 적용하면 성능을 크게 개선할 수 있다.

자바스크립트:

1
2
3
4
5
6
7
8

// 메모이제이션을 적용한 피보나치 함수
const memo = [0, 1];
function fibonacciMemo(n) {
  if (n >= memo.length) {
    memo[n] = fibonacciMemo(n-1) + fibonacciMemo(n-2);
  }
  return memo[n];
}

파이썬:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# 메모이제이션 없는 버전
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

# 메모이제이션 적용 버전
def fib_memo(n, memo={}):
    # 이미 계산된 값이면 바로 반환
    if n in memo:
        return memo[n]
    
    # 기본 케이스
    if n <= 1:
        return n
        
    # 새로운 값 계산 및 저장
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

# 성능 비교
import time

n = 35
start = time.time()
print(f"일반 재귀 결과: {fib(n)}")
print(f"소요 시간: {time.time() - start:f}초")

start = time.time()
print(f"메모이제이션 결과: {fib_memo(n)}")
print(f"소요 시간: {time.time() - start:f}초")

메모이제이션의 구현 방법

  1. 객체나 배열을 사용하여 계산 결과를 저장한다.
  2. 함수 호출 시 먼저 저장된 결과가 있는지 확인한다.
  3. 저장된 결과가 없으면 계산을 수행하고 결과를 저장한다.

메모이제이션의 주의점

  1. 메모리 사용량 증가: 결과를 저장하기 위해 추가적인 메모리가 필요하다.
  2. 적용 대상 선택: 순수 함수(같은 입력에 항상 같은 출력을 반환하는 함수)에 적용하는 것이 좋다.
  3. 캐시 관리: 저장된 결과가 너무 많아지면 메모리 문제가 발생할 수 있으므로, 적절한 캐시 관리가 필요할 수 있다.

실제 적용 사례

  1. 웹 개발: API 호출 결과 캐싱

    1
2
3
4
5
6
7
8
9

    def get_user_data(user_id, cache={}):
    if user_id in cache:
        return cache[user_id]

    # API 호출로 데이터 가져오기
    data = api.get_user(user_id)
    cache[user_id] = data

    return data

  2. 알고리즘: 동적 프로그래밍 문제 해결

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

    def knapsack(weights, values, capacity, memo={}):
    key = (len(weights), capacity)

    if key in memo:
        return memo[key]

    if not weights or capacity <= 0:
        return 0

    if weights[0] > capacity:
        memo[key] = knapsack(weights[1:], values[1:], capacity, memo)
    else:
        memo[key] = max(
            values[0] + knapsack(weights[1:], values[1:], capacity - weights[0], memo),
            knapsack(weights[1:], values[1:], capacity, memo)
        )
    return memo[key]

  3. 그래픽 처리: 복잡한 렌더링 결과 저장

참고 및 출처