메모이제이션(Memoization)

메모이제이션은 동적 프로그래밍(Dynamic Programming, DP) 기법 중 하나로,

이미 계산한 값을 저장하여 중복 계산을 피하고 속도를 개선하는 방법이다.

특히 재귀 알고리즘에서 같은 문제를 반복적으로 호출할 때 유용하게 사용된다.

 

원리

 

1. 이미 계산한 문제를 저장한다.

 - 어떤 함수가 이미 계산한 값을 저장해 두었다가, 같은 입력으로 호출될 때 저장된 값을 반환하여 재계산을 피한다.

2. 재귀 호출의 최적화

 - 반복적으로 호출되는 동일한 연산을 저장된 값을 통해 빠르게 참조하므로 계산 속도가 빨라진다.

3. 탑다운 접근법

 - 메모이제이션은 주로 탑다운 (Top-Down) 방식에서 많이 쓰인다. 주어진 문제를 큰 문제에서 점점 작은 문제로 쪼개면서 풀어가는 방식은, 각각 작은 문제의 값을 저장해가면서 최종 결과를 도출하기 때문에 메모이제이션과 관련이 깊다.

 

 

장점

1. 효율성 : 재귀적 호출을 통한 중복 계산을 줄여 시간복잡도 개선

2. 시간 절약 : 중복 계산이 많이 발생하는 문제에서 시간이 많이 절약됨

 

활용 예

 - 피보나치 수열

 - 최대 경로 문제 (Ex.  삼각형의 최대 경로 합)

 - 배낭 문제 (Knapsack Problem)

 - 조합 계산 (Ex. 파스칼의 삼각형, 이항 계수)

 

 

예제 : 피보나치 수열

피보나치 수열은 대표적인 재귀 문제로, 메모이제이션을 통해 계산 효율을 크게 개선할 수 있다.

피보나치 수열은 각 수가 이전 두 수의 합으로 정의되는 수열이다.

F(n) = F(n-1) + F(n-2)

중복 계산이 많기 때문에 메모이제이션을 사용하면 효과적이다.

 

import java.io.IOException;
import java.util.HashMap;
import java.util.Map;

public class Main {

    // 값을 저장하기 위해 Map 자료구조 사용 (메모이제이션)
    private static Map<Integer, Long> memo = new HashMap<>();
    
    public static void main(String[] args) throws IOException {
        int n = 50; // 50번째 피보나치 수를 구해보자.
        System.out.println("Fibonacci(" + n + ") = " + fibonacci(n));
        
    }
    
    // 재귀함수
    public static long fibonacci(int n) {
        // 기저 조건
        if (n <= 1) return n;
        
        // ***** 메모이제이션 : 이미 계산된 값이 있으면 반환 *****
        if (memo.containsKey(n)) return memo.get(n);
        
        // 이미 계산된 값이 없으면 재귀 호출 후 값 저장
        long result = fibonacci(n - 1) + fibonacci(n - 2);
        memo.put(n, result);
        
        return result;
    }
}