Memoization (메모이제이션)

 

❐ Description

---

[LeetCode#198. House Robber] 문제를 풀면서 메모이제이션 방식에 능숙하지 않음을 파악했고,

간단한 예제와 함께 두 가지(top-down / bottom-up) 방식을 숙달하자. 

 

 

 

 

 

❐ 메모이제이션이란?

---

메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을

메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 

특히 동적계획법(DP)의 핵심이 되는 기술이다. 주로 배열 또는 맵을 이용해서 결과를 저장한다. 

 

 

 

 

 

❐ 구현하는 두 가지 방식

---

1. Top-Down (하향식)

재귀 기반의 접근으로, 문제를 더 작은 하위 문제로 나누어 풀어가며, 이미 계산한 결과를 저장하고 재사용한다.

 

👍 장점 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

• 이해하기 쉽고, 코드가 간경하게 작성된다.
• 필요한 부분만 계산하므로, 경우에 따라 불필요한 계산을 줄일 수 있다.

 

👎 단점 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

• 재귀 호출 스택이 깊어질 수록 스택 오버플로우가 발생할 수 있다.
• 캐싱을 위한 추가 메모리가 필요하다.

 

🧩 예제 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

피보나치 수열을 Top-Down 방식으로 구현해봤다.

public class TopDown {
    
    private static int[] memo;
    
    public int fibonacci(int n) {
        if (n <= 1) return n;
        if (memo[n] != -1) return memo[n];
        // Top ➔ Down
        return memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
    }
    
    public static void main(String[] args) {
        int n = 10;
        memo = new int[n + 1];
        Arrays.fill(memo, -1); // 메모이제이션 배열 초기화

        TopDown topDown = new TopDown();
        topDown.fibonacci(n);
    }
}

 

 

2. Bottom-Up (상향식)

반복문 기반의 접근으로, 작은 문제를 먼저 계산하여 더 큰 문제를 해결하는 방식이다.

 

👍 장점 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

• 스택 오버플로우 문제가 발생하지 않는다.
• 재귀 호출이 없기 때문에 함수 호출 오버헤드가 없다.

 

👎 단점 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

• 모든 하위 문제를 계산해야 하므로, 불필요한 계산이 포함될 가능성이 있다.
• 초기화를 포함해 코드가 Top-Down 보다 조금 복잡할 수 있다.

 

🧩 예제 ⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯

피보나치 수열을 Bottom-Up 방식으로 구현해봤다.

public int fibonacci(int n) {
    if (n <= 1) return n;

    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;

    // Bottom ➔ Top
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 2] + dp[i - 1];
    }
    return dp[n];
}

 

 

 

 

 

❐ 198. House Robber 풀어보기

---

• [LeetCode#198] House Robber 문제풀이 포스팅

 

 

 

 

 

---