"메모이제이션은 아래로 재귀하면서 기억해. 테이블화는 그걸 뒤집어. 가장 작은 답에서 시작해 위로 쌓고, 큰 답이 나올 때까지 테이블을 채워. 같은 DP를 반대 방향으로, 재귀는 하나도 없이."
아래로 재귀하는 대신 위로 짓기
테이블화(tabulation)는 bottom-up 동적 계획법이야. 큰 문제에서 base case로 재귀해 내려가는 대신, base case에서 출발해 테이블을 앞으로 채워 나가. 각 항목은 이미 채운 항목들로 계산하고, 원하는 답에 닿으면 멈춰. 재귀는 없어. 테이블 위를 도는 평범한 루프야. base case가 씨앗이고 마지막 칸이 결과야. 피보나치를 bottom-up으로 하면 dp[0]=0, dp[1]=1로 시작해서 dp[i] = dp[i-1] + dp[i-2]를 n까지 돌리는 거지.
새로운 도전은 딱 하나, 채우는 순서
테이블화의 함정은 순서야. 어떤 항목을 계산하는 시점에 그 항목이 의존하는 값들이 전부 이미 채워져 있도록 순서를 잡아야 해. 피보나치야 왼쪽에서 오른쪽으로, 자명하지. 편집 거리 같은 2D DP라면 행 단위로, 혹은 의존성만 존중한다면 어떤 순서든 좋아. 메모이제이션에서는 이 순서를 신경 쓸 일이 없었어. 재귀가 의존성을 필요한 시점에 알아서 계산해 줬으니까. 테이블화는 그 순서를 직접 생각하게 만들어. 그게 거래야. 재귀를 덜어내는 대가로, 설계 노력을 앞쪽에 더 들이는 거지.
공간의 승리: 필요한 만큼만 들고 가기
테이블화는 메모이제이션이 쉽게 따라오지 못하는 아름다운 최적화 하나를 열어 줘. 테이블 항목이 마지막 행이나 마지막 몇 칸만 읽는 문제가 수두룩하거든. 그렇다면 테이블 전체를 메모리에 둘 이유가 없어. 그 슬라이딩 윈도우만 있으면 돼. 피보나치는 앞의 두 값만 필요하니 O(n) 테이블이 변수 두 개, O(1) 공간으로 주저앉아. O(n×m) 격자가 필요해 보이는 2D DP도 막상 열어 보면 바로 앞 행만 읽는 놈이 태반이라 공간이 O(m)으로 떨어져. '마지막 K칸에만 의존하네'를 알아보는 눈이 DP 공간 비용을 극적으로 줄이는 방법이야. 매번 찾아볼 가치가 있는 반복 트릭이지.
메모이제이션이냐 테이블화냐?
둘은 같은 답을 계산해. 그러니 제약으로 골라. 메모이제이션은 쓰기 쉽고(재귀에 캐시만 얹으면 되니까), 지연이라 필요한 상태만 계산하지만, 재귀 깊이에 묶여. 테이블화는 재귀 한계가 없고 종종 더 빠르고 위의 공간 최적화까지 되지만, 채우기 순서를 설계해야 하고 모든 상태를 계산해. 흔한 작업 흐름은 이래. 메모이제이션으로 프로토타입을 만들어 점화식부터 맞게 잡고, 깊이 안전이나 공간 절약이 필요해지면 테이블화로 변환해. 같은 DP고, 상황 따라 골라 쓰는 거야.