메모이제이션과 동적 계획법(DP): Top-Down vs Bottom-Up 방식

💡 1. 동적 계획법(DP) 개요

동적 계획법(DP)은 문제를 작은 하위 문제로 나누어 해결하는 알고리즘 기법입니다. 반복적인 계산을 피하고 중복 계산을 줄여 성능을 향상시키는 방식입니다.

DP에서 중요한 개념은 중복 계산을 방지하는 것과 최적의 해법을 찾는 것입니다.

---

💡 2. 메모이제이션과 DP: 무엇이 다를까?

메모이제이션은 동적 계획법의 일종입니다. 구체적으로, 메모이제이션은 Top-Down 방식으로 문제를 해결하며, 계산한 결과를 저장하고 재사용하는 기법입니다. DP의 Bottom-Up 방식은 작은 문제부터 차례대로 해결하여 큰 문제를 풀어가는 방식입니다.

 

방법	방식	설명
메모이제이션	Top-Down 방식	재귀를 이용하여 큰 문제를 먼저 해결하고, 작은 문제를 나누어 해결. 중복 계산을 줄이기 위해 결과를 저장하여 재사용.
동적 계획법(DP)	Bottom-Up 방식	작은 문제부터 차례대로 해결하여 큰 문제를 해결. 반복문을 사용하여 최적화된 값을 계산.

---

💡 3. Top-Down 방식과 Bottom-Up 방식

3.1 Top-Down 방식

Top-Down 방식은 재귀를 이용하여 문제를 해결하는 방식입니다. 큰 문제를 먼저 해결하려고 시도하고, 그 후 작은 문제를 풀어 나가는 방식입니다. 중간에 계산한 값은 메모이제이션 기법을 사용하여 저장해두고, 재사용합니다.

예시: 피보나치 수열 (재귀 + 메모이제이션)

      
      
      
    
function fibonacci(n, memo = {}) {
    if (n in memo) return memo[n];  // 이미 계산한 값은 재사용
    if (n === 0) return 0;
    if (n === 1) return 1;
    
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo); // 계산 후 저장
    return memo[n];
}

console.log(fibonacci(10)); // 55

3.2 Bottom-Up 방식

Bottom-Up 방식은 반복문을 사용하여 문제를 해결하는 방식입니다. 작은 문제를 먼저 해결하고, 그 결과를 이용해 점차 큰 문제를 해결해 나가는 방식입니다.

예시: 피보나치 수열 (반복문 + DP)

      
      
      
    
function fibonacci(n) {
    if (n === 0) return 0;
    if (n === 1) return 1;
    
    let a = 0, b = 1;
    for (let i = 2; i <= n; i++) {
        [a, b] = [b, a + b];  // 두 개의 변수만 사용
    }
    return b;
}

console.log(fibonacci(10)); // 55​

💡 4. 재귀 vs 반복문

• 재귀(Recursive): 문제를 하위 문제로 분해할 수 있을 때 유용하며, Top-Down 방식에서 많이 사용됩니다. 하지만 스택 메모리가 많이 사용되므로 메모리 관리에 주의해야 합니다.
• 반복문(Iterative): Bottom-Up 방식에서 사용되며, 반복문을 통해 작은 문제부터 해결합니다. 반복문은 재귀보다 메모리 사용이 효율적입니다.

---

💡 5. 메모이제이션 vs 동적 계획법

• 메모이제이션: Top-Down 방식의 재귀를 사용하여 계산한 값을 저장하여 불필요한 중복 계산을 방지합니다.
• 동적 계획법(DP): Bottom-Up 방식으로, 작은 문제부터 풀어 나가면서 반복문을 사용하여 최적의 값을 계산합니다.

💡 6. 시간 복잡도와 공간 복잡도

• Top-Down 방식 (메모이제이션):
  • 시간 복잡도: O(n) (중복 계산을 피하고, 각 하위 문제는 한 번만 계산)
  • 공간 복잡도: O(n) (재귀 스택 메모리와 저장된 값들)
• Bottom-Up 방식 (동적 계획법):
  • 시간 복잡도: O(n) (작은 문제부터 해결하며, 계산된 값을 재사용)
  • 공간 복잡도: O(n) (배열에 저장된 값들)
    → 공간 최적화: O(1) (배열 대신 2개의 변수만 사용하여 공간을 절약)

---

💡 7. 언제 Top-Down 방식을 사용하고, 언제 Bottom-Up 방식을 사용할까?

• Top-Down 방식 (재귀 + 메모이제이션):
  • 문제의 크기가 매우 클 때
  • 재귀가 자연스러운 경우 (예: 트리 탐색)
  • 구현이 직관적이고 이해하기 쉬운 경우
• Bottom-Up 방식 (반복문 + DP):
  • 작은 문제부터 차례대로 해결할 때
  • 중간 값을 저장하는 것이 효율적인 경우
  • 메모리 사용을 최적화하고자 할 때

---

💡 8. 결론

• 메모이제이션과 동적 계획법은 중복 계산을 피하는 기법으로, Top-Down 방식과 Bottom-Up 방식으로 나뉩니다.
• Top-Down 방식은 재귀를 사용하여 큰 문제를 먼저 해결하고, 작은 문제로 내려가며 계산한 결과를 저장하고 재사용합니다.
• Bottom-Up 방식은 반복문을 사용하여 작은 문제부터 차례대로 해결하고, 큰 문제를 해결합니다.
• 각각의 방식은 문제의 성격과 구현의 용이성에 따라 선택될 수 있습니다.

---

📚 참고 자료

• YouTube 검색: "Dynamic Programming Tutorial"