메모이제이션(Memoization): 중복 연산을 줄이는 최적화 기법

🔹 메모이제이션이란?

1. 메모이제이션(Memoization)의 정의

메모이제이션(Memoization)은 이미 계산된 결과를 저장하고, 동일한 계산이 필요할 때 저장된 값을 재사용하여 중복 연산을 방지하는 최적화 기법입니다.

✅ 메모이제이션의 주요 특징:

• 중복 계산을 줄여 성능을 향상
• 동적 계획법(DP)과 함께 사용되는 경우가 많음
• 시간 복잡도를 줄여 더 빠른 연산 가능
• 재귀 함수와 함께 사용하면 효과적

📌 메모이제이션을 사용하면 연산 속도를 비약적으로 개선할 수 있습니다.

---

🔹 메모이제이션의 동작 과정

1. 함수를 호출하면 먼저 저장된 결과가 있는지 확인
2. 저장된 값이 있으면 그대로 반환 (중복 연산 방지)
3. 저장된 값이 없으면 연산을 수행하고 결과를 저장
4. 필요할 때 저장된 값을 재사용하여 성능 최적화

✔️ 메모이제이션을 활용한 피보나치 수열 예제 (Python):

# 메모이제이션을 적용한 피보나치 함수

def fibonacci_memo(n, memo={}):
    if n in memo:
        return memo[n]  # 저장된 값 반환
    if n <= 1:
        return n
    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]

print(fibonacci_memo(10))  # 출력: 55

📌 메모이제이션을 사용하면 중복 계산을 방지하여 빠른 연산이 가능합니다.

---

🔹 메모이제이션 vs 일반 재귀 비교

✔️ 기본 재귀 방식 (O(2^n)) - 비효율적

# 중복 연산이 많은 기본 재귀 방식의 피보나치 함수

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(10))  # 출력: 55 (매우 느림)

📌 중복 계산이 많아 성능이 저하됩니다.

✔️ 메모이제이션 적용 (O(n)) - 최적화

# 메모이제이션 적용으로 최적화한 피보나치 함수

def fibonacci_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]

print(fibonacci_memo(10))  # 출력: 55 (빠름)

📌 연산 결과를 저장하여 불필요한 계산을 제거합니다.

---

🔹 메모이제이션이 사용되는 문제 유형

1. 동적 계획법(DP) 문제

✅ DP의 탑다운(Top-Down) 방식에서 메모이제이션이 자주 활용됨
✔️ 0-1 배낭 문제, LCS(최장 공통 부분 수열), 최소 편집 거리 문제 등

2. 중복 계산이 많은 재귀적 문제

✅ 피보나치 수열, 하노이의 탑, 경로 찾기 등
✔️ 메모이제이션을 적용하면 성능이 비약적으로 향상됨

3. 캐싱을 활용한 최적화 문제

✅ 웹 페이지 캐싱, 데이터베이스 쿼리 최적화 등에 활용
✔️ 이전에 계산한 결과를 저장하고 재사용

📌 중복 계산이 많은 문제에서는 항상 메모이제이션을 고려해야 합니다.

---

🔹 메모이제이션과 테이블 저장 방식 비교

기법	방식	사용 사례
메모이제이션(Memoization)	재귀(Top-Down)	피보나치, DP, 백트래킹
테이블 저장(Tabulation)	반복문(Bottom-Up)	DP 최적화, 배낭 문제

📌 메모이제이션은 재귀 기반, 테이블 저장 방식은 반복문 기반입니다.

---

📌 결론

✅ 메모이제이션(Memoization)은 중복 연산을 방지하여 성능을 최적화하는 강력한 기법입니다.
✅ 동적 계획법(DP)과 함께 사용되며, 특히 재귀적 문제에서 유용합니다.
✅ 탑다운 방식에서 사용되며, 테이블 저장 방식(Bottom-Up)과 함께 비교할 수 있습니다.
✅ 웹 개발, 데이터 처리, 알고리즘 문제 해결 등 다양한 분야에서 활용됩니다.