메모이제이션 테이블이란?

메모이제이션 테이블은 동적 계획법(Dynamic Programming)에서 중복 계산을 피하기 위해 사용되는 테이블입니다. 동적 계획법은 큰 문제를 작은 하위 문제로 나누어 해결하고, 작은 하위 문제의 해답을 저장하여 중복 계산을 피하는 방법입니다.

메모이제이션 테이블은 이전에 계산한 값을 저장하는 역할을 합니다. 이를 통해 동일한 입력에 대한 계산이 여러 번 필요할 때, 이미 계산된 값을 다시 계산하는 대신 메모이제이션 테이블에서 값을 조회하여 중복 계산을 피할 수 있습니다. 이는 알고리즘의 실행 속도를 향상시키는데 도움이 됩니다.

주로 1차원 배열, 2차원 배열 또는 객체 형태의 메모이제이션 테이블이 사용됩니다. 각 위치에는 하위 문제의 해답이 저장되며, 이를 통해 중복 계산을 효율적으로 피할 수 있습니다. 예를 들어, 피보나치 수열의 경우 n번째 항을 계산할 때 이전에 계산한 항들의 값을 메모이제이션 테이블에 저장하여 중복 계산을 피합니다.

예를 들어 피보나치 수열을 계산하는 함수를 동적 계획법과 메모이제이션 테이블을 활용하여 구현한다고 가정해봅시다. 일반적인 재귀 함수로 피보나치 수열을 계산할 경우 중복 계산이 많이 발생합니다. 이를 해결하기 위해 메모이제이션 테이블을 사용하여 중복 계산을 피할 수 있습니다.

function fibonacci(n, memo = []) {
  if (n <= 1) {
    return n;
  }

  if (memo[n] !== undefined) {
    return memo[n];
  }

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

console.log(fibonacci(5)); // 5
console.log(fibonacci(10)); // 55
console.log(fibonacci(20)); // 6765

위 코드에서 memo 배열은 메모이제이션 테이블로 사용됩니다. memo 배열의 각 인덱스는 해당 인덱스에 대한 피보나치 수열의 값을 저장합니다. 이미 계산한 값이 memo 배열에 존재할 경우 해당 값을 바로 반환하여 중복 계산을 피합니다. 이를 통해 피보나치 수열을 효율적으로 계산할 수 있습니다.

다른 예제로는 동적 계획법과 메모이제이션을 활용하여 이항 계수(Binomial Coefficient)를 계산하는 함수를 구현해보겠습니다. 이항 계수는 조합론에서 주로 사용되며, n개의 원소에서 r개를 선택하는 조합의 개수를 나타냅니다.

function binomialCoefficient(n, r, memo = []) {
  if (r === 0 || r === n) {
    return 1;
  }

  if (memo[n] && memo[n][r] !== undefined) {
    return memo[n][r];
  }

  if (!memo[n]) {
    memo[n] = [];
  }

  memo[n][r] = binomialCoefficient(n - 1, r - 1, memo) + binomialCoefficient(n - 1, r, memo);
  return memo[n][r];
}

console.log(binomialCoefficient(5, 2)); // 10
console.log(binomialCoefficient(10, 3)); // 120
console.log(binomialCoefficient(15, 5)); // 3003

위 코드에서 memo 배열은 이항 계수 값을 저장하는 메모이제이션 테이블입니다. 이미 계산한 이항 계수 값이 memo 배열에 존재할 경우 해당 값을 바로 반환하여 중복 계산을 피합니다. 이를 통해 이항 계수를 효율적으로 계산할 수 있습니다.