망할놈의 알고리즘 - DP편(1) : 메모이제이션과 타뷸레이션

Ref : Introduction to ALGORITHMS, Third Edition, Thomas H. Cormen

Ref : C++ DS and ALgoriithm Design Principles, Jon carry.

※ 해당 게시글을 이해하기 위해서는 자료구조에 대한 기초적인 지식과 적당한 Python/CPP 능력이 필요합니다.

---

머리를 씁시다 머리를

쨋든 DP의 기법들인 Memoization/Tabulation을 알아봅시다. (참고로 Memorization이랑 헷갈리시면 곤란합니다.)

 

메모이제이션은 대게 하향식 방식에서 부분문제의 답을 캐시에 넣어 사용할때를 말합니다. 대게 재귀를 쓰고, 필요한 값만 요청될 때 계산합니다. 또한 다음 조건을 만족할때 성립하게 됩니다.

1. 부분 문제 해법을 캐시에 인덱싱하여 저장하는 방법이 유용해야 함
2. Stack Overflow가 발생할 일이 없어야 함. (대게 Function Stack은 1~16Mb)

사실 DP의 핵심은 타뷸레이션에 있습니다! Memoization이 참 정신건강에는 좋고 편리합니다만, Ref의 저자에 따르면 타뷸레이션을 더 많이 의식해서 사용합니다. 이때 Tabulation은 기저 조건 부터 시작해서 모든 부분문제에 대한 해답을 표에 저장한 후(즉, 한번 미리 계산해 놓는 셈입니다.) 이걸 가져다 사용하는 방식입니다. 이는 메모리 효율적이고, Look-Up table(가능한 모든 상태에 대한 정답)을 생성할 수 있습니다. 

 

근데 이렇게만 말하면 뭔지 모르겠으니까, 대충 문제를 보면서 살펴 봅시다.

 

---

 

 

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. (백준 9095, 0<n<12)

일단 타뷸레이션을 써봅시다. 그리고 이를 위한 캐시에는 뭐 여러가지를 쓸 수 있겠으나, 정수 인덱스 배열/해시 테이블 등이 있을 겁니다. 파이썬에서는 그냥 리스트를 생각해 볼 수 있고, CPP에서는 std::vector/map 정도가 있겠네요. 근데 문제가 일단 서브 문제로 접근이 가능 한지 확인해야 합니다.

 

대충 결과값을 f(n)이라고 해봅시다. f(n)을 무지성(...)으로 나열해 보면 1, 2, 4, 6, 10..과 같이 됩니다. 그리고 여기에서 관찰할 수 있는 점은 - 부분 문제의 해법이 또다른 부분문제의 답이 들어간다는 점입니다. 대충 DP 써보이기 딱 좋아보이죠. 해서 아래와 같이 파이썬 코드를 작성해 봅시다.

 

import sys

T = int(input())

data = [1, 2, 4]

for i in range(3, 12):
    data.append(data[i-3] + data[i-2] + data[i-1])

for k in range(T):
    X = int(sys.stdin.readline().strip())
    sys.stdout.write(str(data[X-1]))
    if k != (T-1):
        sys.stdout.write('\n')

 

참고로 표 형식의 데이터라 for/while이 잘 어울립니다. 분기나 다차원 상태 표현은 재귀로 도는게 좋습니다.

 

반면 메모이제이션을 쓰면 대충 아래처럼 하면 됩니다.

import sys

T = int(input())

dp = {}

def f(n):
    if n in dp:
        return dp[n]
    if n <= 3:
        return base[n]
    dp[n] = f(n-1) + f(n-2) + f(n-3)
    return dp[n]

for k in range(T):
    X = int(sys.stdin.readline().strip())
    sys.stdout.write(f(X))
    if k != (T-1):
        sys.stdout.write('\n')

타뷸레이션과의 차이가 보이시나요? 핵심은 필요한 타뷸레이션과는 다르게 메모이제이션은 필요한 값만 "요청될 때" 계산됩니다. 대게 이경우에는 계산해야 되는 수가 무지막지하게 큰데 계산해야 할 수는 적을때 사용합니다. 타뷸레이션은 반대로 쿼리가 여러번 들어올때 / 계산해야 되는 수가 상대적으로 적을때 사용합니다. 물론 막 정해진건 아니라서, 그냥 마음대로 사용하면 됩니다.

 

쨋든 기초적인 DP는 이렇습니다. 문제는 이게 문자열/시퀀스에도 적용되고, 아직 좀 할 얘기가 수두룩 하게 많다는 점이죠...