테이블레이션(Tabulation)

Tabulation은 프로그래밍에서 동적 프로그래밍(Dynamic Programming)의 한 기법으로, 복잡한 문제를 해결하기 위해 사용되는 방법이다.

Tabulation은 ‘표를 만든다’는 의미로, 문제의 해결 과정을 표 형태로 정리하는 기법이다. 이 방법은 작은 부분 문제(subproblem)부터 시작하여 점진적으로 더 큰 문제를 해결해 나가는 상향식(bottom-up) 접근 방식을 사용합니다.

Tabulation의 작동 원리

  1. 문제 정의: 해결하고자 하는 문제와 그 부분 문제들을 명확히 정의한다.
  2. 표 초기화: 부분 문제의 결과를 저장할 표(보통 배열이나 리스트)를 만든다.
  3. 기본 케이스 설정: 가장 작은 부분 문제에 대한 해답을 표에 채운다.
  4. 반복적 계산: 작은 부분 문제부터 시작하여 큰 문제로 나아가며 표를 채운다.
  5. 최종 결과 도출: 표의 마지막 항목이 전체 문제의 해답이 된다.

Tabulation의 예시: 피보나치 수열

피보나치 수열을 계산하는 예시

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

def fibonacci_tabulation(n):
    # 표 초기화
    fib = [0] * (n + 1)
    
    # 기본 케이스 설정
    fib[0] = 0
    fib[1] = 1
    
    # 반복적 계산
    for i in range(2, n + 1):
        fib[i] = fib[i-1] + fib[i-2]
    
    # 최종 결과 반환
    return fib[n]

# 사용 예
print(fibonacci_tabulation(10))  # 55 출력

이 예시에서 표(fib 리스트)는 각 인덱스에 해당하는 피보나치 수를 저장한다.
작은 문제(0번째, 1번째 피보나치 수)부터 시작하여 점진적으로 큰 문제(n번째 피보나치 수)를 해결한다.

Tabulation의 장점

  1. 효율성: 중복 계산을 피하여 시간 복잡도를 개선한다.
  2. 메모리 사용: 필요한 결과만 저장하므로 메모리를 효율적으로 사용한다.
  3. 예측 가능성: 반복문을 사용하여 실행 시간을 예측하기 쉽다.

참고 및 출처