DP 타뷸레이션: 작은 답부터 테이블 채우기

타뷸레이션은 필요한 작은 답을 먼저 채워 큰 답으로 올라가는 방식입니다. 계산하려는 칸보다 먼저 필요한 칸이 완성돼 있어야 합니다.

선수 지식: 배열 인덱스·반복문과 F(n)=F(n−1)+F(n−2)의 의미를 알아야 합니다.

• 하위 상태가 먼저 완성되는 계산 순서를 정합니다.
• 테이블을 두 변수로 줄일 때의 갱신 순서를 설명합니다.

앞의 두 칸이 채워진 뒤 다음 칸을 씁니다

F(0)=0과 F(1)=1을 배열에 넣고 i=2부터 시작합니다. i번째 값을 채울 때 참조하는 것은 i−1과 i−2뿐입니다. 인덱스가 증가하는 순서라면 두 칸이 이미 완성돼 있다는 사실을 매번 보장할 수 있습니다. for문의 방향은 단순한 취향이 아니라 상태 사이의 의존 관계에서 나옵니다.

반복 직전까지 values[0]부터 values[i−1]이 정확하다는 약속을 유지합니다. 이를 바탕으로 두 값을 더하면 i번째도 정확합니다. 0과 1에서는 반복을 시작하지 않고 바로 반환합니다.

뒤에서 다시 읽지 않는 칸은 보관하지 않아도 됩니다

마지막 답 하나만 필요하다면 오래된 칸을 전부 남길 이유가 없습니다. i번째 값을 계산하기 직전 previous는 F(i−2), current는 F(i−1)입니다. next=previous+current를 먼저 계산합니다. 그다음 previous=current, current=next로 옮기면 같은 약속이 한 단계 뒤로 이동합니다. 첫 변수를 덮어쓴 뒤 그 값으로 두 번째를 계산하면 원래 더해야 할 값 하나를 잃어버립니다.

이 방식은 언제나 테이블을 대체하지는 않습니다. 모든 F(0)~F(n)을 보여 주거나 중간 상태를 이용해 선택 경로를 복원해야 한다면 저장한 칸이 다시 필요합니다. 공간을 줄이는 판단은 입력 크기뿐 아니라 최종적으로 어떤 결과를 요구하는지에서 시작합니다.

메모이제이션과 타뷸레이션의 답은 같아야 합니다

두 방식은 같은 점화식을 계산하므로 같은 입력에서 결과가 일치해야 합니다. 메모이제이션은 요청된 상태부터 내려가고, 타뷸레이션은 의존 순서에 맞게 올라옵니다. 실제 문제가 모든 상태를 요구하지 않는다면 요청한 상태만 푸는 방법이 유리할 수 있습니다. 반대로 이 피보나치처럼 거의 모든 작은 상태를 쓰면 순서가 단순한 반복문을 선택하기 쉽습니다.

테이블 방식도 입력과 정수 범위를 무시할 수는 없습니다. 두 구현 모두 0~78만 허용하며 79, 음수, 소수는 거절합니다. 재귀가 없어졌다는 이유로 Number가 무한한 정수를 정확히 저장한다고 생각하지 않아야 합니다.

전체 코드와 직접 실행

개념을 읽었다면 아래 예제를 직접 실행하며 상태 변화를 확인할 수 있습니다.

function checkFibonacciInput(n) {
  if (!Number.isInteger(n) || n < 0 || n > 78) {
    throw new RangeError('n은 0 이상 78 이하의 정수여야 합니다.');
  }
}

function fibonacciTable(n) {
  checkFibonacciInput(n);
  if (n < 2) return n;
  const values = [0, 1];
  for (let i = 2; i <= n; i++) values[i] = values[i - 1] + values[i - 2];
  return values[n];
}

function fibonacciRolling(n) {
  checkFibonacciInput(n);
  if (n < 2) return n;
  let previous = 0;
  let current = 1;
  for (let i = 2; i <= n; i++) {
    const next = previous + current;
    previous = current;
    current = next;
  }
  return current;
}

console.log(fibonacciTable(10));
console.log(fibonacciRolling(10));

node dp-tabulation.mjs

55
55

비용과 적용 범위

시간: 두 방식 모두 O(n)번 덧셈입니다.

공간: 테이블은 O(n), 두 변수 방식은 O(1) 추가 공간입니다.

분석 조건: 정수 0≤n≤78. 최종 값 하나만 요구할 때 두 변수 최적화가 가능합니다.

직접 확인해 보기

F(6)=8까지 계산한 상태에서 previous=5, current=8입니다. 다음 값을 한 번 계산하면 무엇이 되나요?

함께 읽을 글

• 기초 구현 패턴 — 반복에서 어떤 값을 보관하고 갱신하는지 먼저 익힙니다.
• JavaScript 배열의 연산 비용 — 테이블의 인덱스와 추가 공간 비용을 이해합니다.

참고 자료

• Competitive Programmer’s Handbook — 동적 계획법의 상태·전이, 부분집합과 순회 최적화의 일반 원리를 대조합니다. 예제와 설명은 이 원고의 독립 구현입니다.
• MDN — Number.MAX_SAFE_INTEGER — Number 정수 정밀도의 한계와 이 예제의 피보나치 상한을 구분합니다.