메모이제이션 편집하기

'''메모이제이션'''(Memoization)은 중복되는 연산을 피하기 위해 이전에 계산한 값을 저장하고, 필요할 때 이를 다시 사용하는 '''동적 계획법(Dynamic Programming, DP)''' 기법 중 하나이다. '''Top-Down 방식'''의 동적 계획법에서 주로 사용되며, '''재귀 호출'''을 최적화하는 데 유용하다.
==개요==
메모이제이션은 '''중복 부분 문제(Overlapping Subproblems)'''가 존재하는 경우 효과적으로 사용할 수 있다.
*'''중복 부분 문제''' → 동일한 하위 문제가 여러 번 등장하는 문제.
*'''최적 부분 구조''' → 부분 문제의 최적해를 결합하여 전체 문제의 최적해를 구할 수 있는 구조.
메모이제이션을 적용하면 중복 계산을 제거하여 시간 복잡도를 줄일 수 있다.
==동작 방식==
메모이제이션은 보통 다음과 같은 방식으로 동작한다.
*'''재귀 호출 전에 이미 계산된 값이 있는지 확인.'''
*'''저장된 값이 있다면 해당 값을 반환.'''
*'''저장된 값이 없다면 재귀 호출을 수행하고, 결과를 저장 후 반환.'''
==메모이제이션 vs 테뷸레이션==
메모이제이션은 '''Top-Down(재귀 기반)''' 접근법이고, 테뷸레이션(Tabulation)은 '''Bottom-Up(반복문 기반)''' 접근법이다.
{| class="wikitable"
|-
!기법!!구현 방식!!장점!!단점
|-
!메모이제이션
|재귀 호출 + 해시 테이블(딕셔너리) 또는 배열
|필요한 부분 문제만 계산하여 효율적
|재귀 호출 오버헤드가 발생할 수 있음
|-
!테뷸레이션
|반복문을 사용하여 작은 문제부터 해결
|재귀 호출이 없어 오버헤드가 적음
|모든 하위 문제를 계산해야 할 수도 있음
|}
==예제==
가장 대표적인 예제는 '''피보나치 수열(Fibonacci Sequence)'''이다.
===메모이제이션을 사용하지 않은 재귀===
<syntaxhighlight lang="python">
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(10))  # 출력: 55
</syntaxhighlight>
*위 코드의 시간 복잡도는 '''O(2ⁿ)'''으로 매우 비효율적이다.
===메모이제이션을 사용한 재귀===
<syntaxhighlight lang="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
</syntaxhighlight>
*위 코드의 시간 복잡도는 '''O(n)'''으로 최적화됨.
==메모이제이션이 적용되는 문제==
메모이제이션은 다음과 같은 문제에 효과적이다.
*'''피보나치 수열'''
**중복 계산을 방지하여 O(n)으로 최적화.
*'''배낭 문제(Knapsack Problem)'''
**각 아이템을 넣거나 넣지 않는 경우를 고려.
*'''최장 공통 부분 수열(LCS, Longest Common Subsequence)'''
**문자열 간의 최대 공통 부분 찾기.
*'''최소 편집 거리(Edit Distance)'''
**문자열을 변환하는 최소 연산 횟수 계산.
==시간 복잡도==
메모이제이션을 적용하면 재귀 호출의 중복을 제거할 수 있다.
*'''피보나치 수열'''
**기본 재귀: O(2ⁿ)
**메모이제이션 적용: O(n)
*'''배낭 문제'''
**완전 탐색: O(2ⁿ)
**메모이제이션 적용: O(nW) (W는 배낭 용량)
*'''LCS'''
**완전 탐색: O(2ⁿ)
**메모이제이션 적용: O(nm) (n과 m은 두 문자열 길이)
==응용==
메모이제이션은 다양한 분야에서 활용된다.
*'''컴퓨터 그래픽'''
**반복 연산을 최적화하여 렌더링 속도 향상.
*'''네트워크 경로 탐색'''
**최단 경로를 미리 계산하여 빠른 탐색 가능.
*'''인공지능 및 머신러닝'''
**학습 과정에서 중복 연산을 제거하여 성능 향상.
==같이 보기==
*[[동적 계획법]]
*[[탑다운 방식]]
*[[테뷸레이션]]
*[[배낭 문제]]
*[[빈 패킹 문제]]
*[[삼각 분할]]
==참고 문헌==
*Bellman, Richard. "Dynamic Programming." Princeton University Press, 1957.
*Cormen, Thomas H., et al. "Introduction to Algorithms." MIT Press, 2009.
[[분류:알고리즘]]