메모이제이션(Memoization)이란?
메모이제이션은 동적 프로그래밍(Dynamic Programming)에 기반한 최적화 기술입니다. 주어진 입력값에 대한 연산 결과를 배열과 같은 자료구조에 저장해 두었다가 재사용함으로써, 동일한 입력에 대해 재귀 메서드가 두 번 이상 실행되지 않도록 보장하고 재귀 알고리즘의 성능을 크게 향상시킵니다. 메모이제이션은 재귀 메서드의 탑다운(Top-Down) 방식을 구현하여 적용할 수 있습니다.
가장 기본적인 피보나치(Fibonacci) 수열 예제를 통해 메모이제이션의 필요성을 살펴보겠습니다.
1차원(1-D) 메모이제이션
값이 변하는 매개변수가 단 하나뿐인 재귀 알고리즘에 메모이제이션을 적용하는 방식을 1차원(1-D) 메모이제이션이라고 합니다. 아래 코드는 피보나치 수열의 N번째 항까지 모든 값을 구하는 순수 재귀 함수입니다.
예제
public int fibonacci(int n) {
if (n == 0)
return 0;
if (n == 1)
return 1;
System.out.println("Calculating fibonacci number for: " + n);
return (fibonacci(n - 1) + fibonacci(n - 2));
}출력 결과
n=5로 위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Calculating fibonacci number for: 5 Calculating fibonacci number for: 4 Calculating fibonacci number for: 3 Calculating fibonacci number for: 2 Calculating fibonacci number for: 2 Calculating fibonacci number for: 3 Calculating fibonacci number for: 2
Fibonacci value for n=5: 5
출력 결과를 보면 F(2)와 F(3)가 불필요하게 여러 번 계산되는 것을 확인할 수 있습니다. n=5일 때의 재귀 트리를 그려보면 더 명확하게 이해할 수 있습니다. 트리에서 각 노드의 두 자식 노드는 해당 노드가 수행하는 재귀 호출을 나타냅니다. 그림에서 볼 수 있듯이 F(3)과 F(2)는 중복해서 계산되며, 각 단계마다 결과를 캐싱하면 이러한 중복 연산을 피할 수 있습니다.
여기서는 인스턴스 변수인 memoizeSet(HashMap)을 사용하여 결과를 캐싱합니다. 먼저 해당 입력값 n이 이미 캐시에 존재하는지 확인하고, 존재한다면 저장된 값을 즉시 반환합니다. 존재하지 않는 경우에는 값을 새로 계산한 뒤 캐시에 추가합니다.
예제
import java.util.HashMap;
import java.util.Map;
public class TutorialPoint {
private Map<Integer, Integer> memoizeSet = new HashMap<>(); // O(1)
public int fibMemoize(int input) {
if (input == 0)
return 0;
if (input == 1)
return 1;
if (this.memoizeSet.containsKey(input)) {
System.out.println("Getting value from computed result for " + input);
return this.memoizeSet.get(input);
}
int result = fibMemoize(input - 1) + fibMemoize(input - 2);
System.out.println("Putting result in cache for " + input);
this.memoizeSet.put(input, result);
return result;
}
public static void main(String[] args) {
TutorialPoint tutorialPoint = new TutorialPoint();
System.out.println("Fibonacci value for n=5: " + tutorialPoint.fibMemoize(5));
}
}출력 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Putting result in cache for 2 Putting result in cache for 3 Getting value from computed result for 2 Putting result in cache for 4 Getting value from computed result for 3 Putting result in cache for 5
Fibonacci value for n=5: 5
출력에서 볼 수 있듯이 F(2)와 F(3)는 더 이상 중복 계산되지 않습니다. HashMap 기반의 메모이제이션 캐시를 도입하여, 피보나치 값을 계산하기 전에 먼저 해당 입력값에 대한 결과가 이미 캐시에 저장되어 있는지 확인하고, 없는 경우에만 새로 계산한 값을 캐시에 추가하는 방식으로 동작합니다.
2차원(2-D) 메모이제이션
앞선 예제에서는 값이 변하는 매개변수가 하나뿐이었습니다. 이번에는 재귀 호출마다 값이 변하는 매개변수가 두 개인 재귀 프로그램에 메모이제이션을 적용하여 최적화하는 방법을 알아보겠습니다. 이를 2차원(2-D) 메모이제이션이라고 합니다.
대표적인 예로 최장 공통 부분 수열(Longest Common Subsequence, LCS) 문제가 있습니다. 여러 개의 문자열이 주어졌을 때, LCS 문제는 모든 문자열에 공통으로 나타나는 부분 수열 중 길이가 최대인 것을 찾는 문제입니다. 가능한 조합의 수는 2ⁿ개에 이르므로, 순수 재귀로 해결하면 비효율적입니다.
예제
class TP {
static int computeMax(int a, int b) {
return (a > b) ? a : b;
}
static int longestComSs(String X, String Y, int m, int n) {
if (m == 0 || n == 0)
return 0;
if (X.charAt(m - 1) == Y.charAt(n - 1))
return 1 + longestComSs(X, Y, m - 1, n - 1);
else
return computeMax(longestComSs(X, Y, m, n - 1),
longestComSs(X, Y, m - 1, n));
}
public static void main(String[] args) {
String word_1 = "AGGTAB";
String word_2 = "GXTXAYB";
System.out.print("Length of LCS is "
+ longestComSs(word_1, word_2,
word_1.length(), word_2.length()));
}
}출력 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Length of LCS is 4
재귀 트리의 중간 과정을 살펴보면 lcs("AXY", "AYZ") 같은 동일한 부분 문제가 여러 번 반복해서 해결되는 것을 확인할 수 있습니다. 이 문제는 중복되는 하위 구조(Overlapping Substructure) 특성을 가지므로, 메모이제이션 또는 태뷸레이션(Tabulation)을 활용하면 동일한 하위 문제의 중복 계산을 피할 수 있습니다.
재귀 코드에 메모이제이션을 적용한 구현은 다음과 같습니다.
예제
import java.io.*;
import java.lang.*;
class testClass {
final static int maxSize = 1000;
public static int arr[][] = new int[maxSize][maxSize];
public static int calculatelcs(String str_1, String str_2, int m, int n) {
if (m == 0 || n == 0)
return 0;
if (arr[m - 1][n - 1] != -1)
return arr[m - 1][n - 1];
if (str_1.charAt(m - 1) == str_2.charAt(n - 1)) {
arr[m - 1][n - 1] = 1 + calculatelcs(str_1, str_2, m - 1, n - 1);
return arr[m - 1][n - 1];
} else {
int a = calculatelcs(str_1, str_2, m, n - 1);
int b = calculatelcs(str_1, str_2, m - 1, n);
int max = (a > b) ? a : b;
arr[m - 1][n - 1] = max;
return arr[m - 1][n - 1];
}
}
public static void main(String[] args) {
for (int i = 0; i < 1000; i++) {
for (int j = 0; j < 1000; j++) {
arr[i][j] = -1;
}
}
String str_1 = "AGGTAB";
String str_2 = "GXTXAYB";
System.out.println("Length of LCS is "
+ calculatelcs(str_1, str_2,
str_1.length(), str_2.length()));
}
}출력 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Length of LCS is 4
접근 방식
calculatelcs 메서드는 총 4개의 인자를 받습니다. 이중 2개는 상수(문자열)로 메모이제이션 대상이 아니며, 나머지 2개의 비상수 인자(m과 n)가 재귀 호출 시마다 값이 변합니다. 따라서 메모이제이션을 구현하기 위해 2차원 배열을 도입하여 lcs(m, n)의 계산 결과를 arr[m-1][n-1]에 저장합니다. 이후 동일한 m과 n으로 함수가 다시 호출되면 추가적인 재귀 호출을 수행하지 않고 이미 저장된 arr[m-1][n-1] 값을 즉시 반환함으로써, 재귀 호출 횟수를 최소화할 수 있습니다.
3차원(3-D) 메모이제이션
3차원(3-D) 메모이제이션은 값이 변하는 매개변수가 세 개인 재귀 프로그램에 메모이제이션을 적용하는 방식입니다. 여기서는 세 개의 문자열에 대한 LCS 길이를 구하는 예제를 살펴보겠습니다.
기본 아이디어는 주어진 문자열들에 대해 가능한 모든 부분 수열(총 가능한 부분 수열의 수는 3ⁿ개)을 생성한 뒤, 그중 가장 긴 공통 부분 수열을 찾는 것입니다. 이를 위해 계산된 값을 저장할 3차원 테이블을 사용합니다. 다음과 같은 부분 수열을 고려해 보겠습니다.
- A1[1...i], i < N
- A2[1...j], j < M
- A3[1...k], k < K
세 문자열에서 공통 문자를 찾으면(X[i]==Y[j]==Z[k]) 나머지 부분에 대해 재귀를 진행합니다. 그렇지 않다면 다음 세 가지 경우 중 최댓값을 계산합니다.
- X[i]를 제외하고 나머지에 대해 재귀
- Y[j]를 제외하고 나머지에 대해 재귀
- Z[k]를 제외하고 나머지에 대해 재귀
이 아이디어를 점화식으로 표현하면 다음과 같습니다.
f(N, M, K) =
• X[N] == Y[M] == Z[K]인 경우: 1 + f(N-1, M-1, K-1)
• 그 외의 경우: maximum(f(N-1, M, K), f(N, M-1, K), f(N, M, K-1))
- f(N-1, M, K): X[i]를 제외하고 재귀
- f(N, M-1, K): Y[j]를 제외하고 재귀
- f(N, M, K-1): Z[k]를 제외하고 재귀
예제
import java.io.IOException;
import java.io.InputStream;
import java.util.*;
class testClass {
public static int[][][] arr = new int[100][100][100];
static int calculatelcs(String str_1, String str_2, String str_3,
int m, int n, int o) {
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
arr[i][j][0] = 0;
}
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= o; j++) {
arr[0][i][j] = 0;
}
}
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= o; j++) {
arr[i][0][j] = 0;
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 1; k <= o; k++) {
if (str_1.charAt(i - 1) == str_2.charAt(j - 1)
&& str_2.charAt(j - 1) == str_3.charAt(k - 1)) {
arr[i][j][k] = 1 + arr[i - 1][j - 1][k - 1];
} else {
arr[i][j][k] = calculateMax(arr[i - 1][j][k],
arr[i][j - 1][k], arr[i][j][k - 1]);
}
}
}
}
return arr[m][n][o];
}
static int calculateMax(int a, int b, int c) {
if (a > b && a > c)
return a;
if (b > c)
return b;
return c;
}
public static void main(String[] args) {
String str_1 = "clued";
String str_2 = "clueless";
String str_3 = "xcxclueing";
int m = str_1.length();
int n = str_2.length();
int o = str_3.length();
System.out.print("Length of LCS is "
+ calculatelcs(str_1, str_2, str_3, m, n, o));
}
}출력 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Length of LCS is 4
마무리
메모이제이션은 재귀 알고리즘에서 발생하는 중복 연산을 제거하는 강력한 최적화 기법입니다. 값이 변하는 매개변수의 개수에 따라 1차원, 2차원, 3차원 배열(또는 Map)을 캐시로 사용하면 되며, 피보나치 수열이나 LCS처럼 중복되는 하위 문제가 많은 문제에서 지수 시간 복잡도를 다항 시간 복잡도로 크게 개선할 수 있습니다.