테뷸레이션(Tabulation)은 동적 계획법(Dynamic Programming, DP)의 한 기법으로, 하위 문제를 모두 해결한 후, 이를 조합하여 최적해를 구하는 방법이다. Bottom-Up 방식을 사용하며, 일반적으로 반복문을 이용하여 DP 테이블을 채운다.

개요

테뷸레이션은 다음과 같은 속성을 가진 문제에서 유용하다.

• 최적 부분 구조(Optimal Substructure)
  • 부분 문제의 최적해를 이용하여 전체 문제의 최적해를 찾을 수 있음.
• 중복 부분 문제(Overlapping Subproblems)
  • 동일한 하위 문제가 여러 번 반복되는 경우, 이를 저장하여 중복 연산을 방지.

테뷸레이션 vs 메모이제이션

테뷸레이션과 메모이제이션은 동적 계획법의 두 가지 구현 방식이다.

동작 방식

테뷸레이션 방식은 다음과 같은 과정을 따른다.

• DP 테이블을 정의하고, 초기 값을 설정.
• 작은 문제부터 순차적으로 해결.
• 하위 문제의 결과를 이용하여 더 큰 문제 해결.

예제 문제

대표적인 동적 계획법 문제 중 하나는 피보나치 수열(Fibonacci Sequence)이다.

테뷸레이션을 사용하지 않은 재귀

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(10))  # 출력: 55

• 위 코드의 시간 복잡도는 O(2ⁿ)으로 매우 비효율적이다.

테뷸레이션을 사용한 반복문

def fibonacci_tabulation(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

print(fibonacci_tabulation(10))  # 출력: 55

• 위 코드의 시간 복잡도는 O(n), 공간 복잡도는 O(n)이다.
• 만약 O(1)의 공간 복잡도를 원하면 배열 대신 변수 두 개를 사용하여 최적화할 수 있다.

테뷸레이션이 적용되는 문제

테뷸레이션은 다음과 같은 문제에서 효과적이다.

• 배낭 문제(Knapsack Problem)
  • 제한된 용량 내에서 최대 가치를 얻도록 아이템을 선택하는 문제.
• 최장 공통 부분 수열(LCS, Longest Common Subsequence)
  • 두 개의 문자열에서 공통 부분 문자열의 최대 길이를 찾는 문제.
• 최소 편집 거리(Edit Distance)
  • 문자열을 변환하는 최소 연산 횟수를 구하는 문제.
• 동전 교환 문제(Coin Change)
  • 최소한의 동전 개수로 특정 금액을 만드는 문제.
• 여행하는 외판원 문제(TSP, Traveling Salesman Problem)
  • 모든 도시를 한 번씩 방문하는 최소 비용의 경로를 찾는 문제.

시간 복잡도

테뷸레이션을 적용하면 문제를 효율적으로 해결할 수 있다.

• 피보나치 수열
  • 기본 재귀: O(2ⁿ)
  • 테뷸레이션 적용: O(n)
• 배낭 문제
  • 완전 탐색: O(2ⁿ)
  • 테뷸레이션 적용: O(nW) (W는 배낭 용량)
• LCS
  • 완전 탐색: O(2ⁿ)
  • 테뷸레이션 적용: O(nm) (n과 m은 두 문자열 길이)

응용

테뷸레이션은 다양한 분야에서 활용된다.

• 데이터 압축
  • 문자열 비교 및 패턴 매칭.
• 네트워크 최적화
  • 최적 경로 탐색 및 패킷 전송 최적화.
• 게임 인공지능
  • 최적의 움직임을 찾는 알고리즘.

같이 보기

• 동적 계획법
• 메모이제이션
• 탑다운 방식
• 배낭 문제

참고 문헌

• Bellman, Richard. "Dynamic Programming." Princeton University Press, 1957.
• Cormen, Thomas H., et al. "Introduction to Algorithms." MIT Press, 2009.