메모이제이션(Memoization)과 탭레이션(Tabulation)의 차이

0. Intro

메모이제이션(Memoization)과 탭레이션(Tabulation)은 둘 다 동적 프로그래밍(Dynamic Programming)에서 사용되는 방법이며, 입력 크기가 작은 하위 문제의 해답을 이용해 큰 문제를 해결하는 방법을 사용합니다. 그러나 두 방법의 차이점은 계산 방식과 구현 방법에서 차이가 있습니다.

 

1. 메모이제이션

Memoization은 top-down 방식으로, 큰 문제를 해결할 때 작은 하위 문제의 해답을 이용합니다. 이 때, 작은 하위 문제의 해답을 기록해 두고, 이를 이용하여 중복 계산을 피합니다. 따라서, 재귀 호출을 사용하여 구현하는 경우가 많습니다.

 

2. 탭레이션

Tabulation은 bottom-up 방식으로, 작은 하위 문제의 해답을 먼저 계산하고, 그것을 이용해 큰 문제의 해답을 계산하는 방식입니다. 이 때, 배열을 사용하여 작은 문제의 해답을 저장하고, 그것을 이용해 큰 문제의 해답을 계산합니다. 따라서, 반복문을 사용하여 구현하는 경우가 많습니다.

 

3. 메모이제이션 vs 텝레이션

Memoization은 재귀 호출을 사용하기 때문에 호출 스택이 늘어날 수 있어 스택 오버플로우 등의 문제가 발생할 수 있습니다. 반면, Tabulation은 반복문을 사용하기 때문에 호출 스택이 늘어나지 않아 이러한 문제가 발생하지 않습니다. 또한, Memoization은 필요한 하위 문제만을 해결하는 경우가 많은 반면, Tabulation은 전체 하위 문제의 해답을 구하고, 이를 이용하여 큰 문제의 해답을 구하기 때문에 메모리 사용량이 더 많을 수 있습니다.

 

따라서, 어떤 방법을 사용할지는 문제의 성격에 따라 다르게 결정됩니다. 일반적으로, 재귀적인 구조를 가진 문제에 대해서는 Memoization을, 반복문을 사용하여 구현하기 쉬운 문제에 대해서는 Tabulation을 사용하는 경우가 많습니다.