시스매

타뷸레이션

4 min read

2025-09-01 02:00

Tags: 알고리즘 자료구조

타뷸레이션

동적 계획법 타뷸레이션

  • 가장 작은 문제부터 차례대로 해결해 최종 답 구하는 상향식 접근법
  • 재귀 호출의 비효율성(중복 계산, 스택 오버플로우) 해결하기 위해 반복문 사용해서 DP 테이블 채워나가는 식으로 동작
  • 메모이제이션과 마찬가지로 동적 계획법이지만 재귀 없이 반복문으로 구현

작동 방식

  1. 테이블 만들기: 해결해야 할 문제의 크기에 맞게 DP 테이블을 생성합니다.
  2. 초기값 설정: 가장 작은 문제, 즉 우리가 이미 답을 알고 있는 ‘베이스 케이스(Base Case)‘에 해당하는 값을 테이블에 미리 채워 넣습니다.
  3. 점화식 기반 반복: 반복문을 통해 테이블을 순회하며, 이전에 계산된 값들(더 작은 하위 문제의 답)을 이용하여 다음 칸의 값을 계산합니다. 이때 사용되는 규칙이 바로 ‘점화식(Recurrence Relation)‘입니다.
  4. 최종 결과 도출: 반복문이 모두 끝나면 테이블이 완성됩니다. 우리가 원하는 최종 문제의 답은 테이블의 특정 위치(보통 가장 마지막 칸)에 저장되어 있습니다.

피보나치 예시

  1. 테이블 만들기: n까지의 피보나치 수를 저장해야 하므로, 크기가 n+1인 1차원 배열 dp를 만듭니다. dp[i]는 i번째 피보나치 수를 의미합니다.
  2. 초기값 설정: 피보나치 수열의 가장 작은 문제는 fib(0)과 fib(1)입니다. 우리는 fib(0) = 0, fib(1) = 1임을 이미 알고 있습니다. 따라서 dp[0] = 0, dp[1] = 1로 설정합니다.
  3. 점화식 기반 반복: 피보나치 수열의 점화식은 fib(i) = fib(i-1) + fib(i-2)입니다. 이를 우리 DP 테이블에 맞게 바꾸면 dp[i] = dp[i-1] + dp[i-2]가 됩니다. 이제 i를 2부터 n까지 순회하는 반복문을 만들어 이 점화식을 적용합니다.
  4. 최종 결과 도출: 반복문이 끝나면 dp[n]에 우리가 원하는 n번째 피보나치 수가 저장되어 있습니다.
def fibonacci_tabulation(n):
    if n <= 1:
        return n
    
    # 1. 테이블 만들기
    dp = [0] * (n + 1)
    
    # 2. 초기값 설정
    dp[1] = 1
    
    # 3. 점화식 기반 반복
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
        
    # 4. 최종 결과 도출
    return dp[n]
 
print(fibonacci_tabulation(10)) # 결과: 55

그래프 뷰

백링크