4.1 메모이제이션의 정의와 주요 개념
메모이제이션은 시간 소모가 큰 함수의 결과를 저장하여 동일한 인자로 다시 호출했을 때 결과를 재활용하는 최적화 기술이야. 이렇게 하면 반복 계산을 줄이고 성능을 높일 수 있지.
주요 개념들:
1. 캐싱:
함수 결과를 사전이나 배열 같은 데이터 구조에 저장하여 동일한 인자로 다시 호출했을 때 이미 저장된 결과를 반환하는 거야, 새로 계산하지 않고.
2. 조회 테이블 (Lookup Table):
이전 함수 호출의 결과를 저장하기 위한 데이터 구조야. 해시 테이블(사전)이나 배열이 될 수 있어.
3. 재귀 호출:
메모이제이션은 특히 동일한 매개변수로 여러 번 호출될 수 있는 재귀 함수에 유용해.
최적화된 알고리즘의 시간 및 공간 복잡도:
시간 복잡도:
많은 재귀적 문제에서 메모이제이션은 반복 계산을 줄여 시간 복잡도를 낮춰줘. 예를 들어, 피보나치 수열의 재귀적 계산은 O(2^n) 시간이 걸리지만, 메모이제이션을 사용하면 O(n)으로 줄어들어.
공간 복잡도:
결과를 캐시에 저장하기 때문에 공간 복잡도가 증가해. 일반적으로 메모이제이션이 필요한 문제의 경우 O(n)야.
요약:
메모이제이션은 반복 계산을 줄여 재귀 알고리즘의 성능을 크게 개선할 수 있는 강력한 최적화 기술이야.
동일한 매개변수로 여러 번 호출될 수 있는 하위 문제에 특히 유용해. 메모이제이션의 개념을 이해하고 실전에서 활용하면 계산 부하가 높은 문제를 효율적으로 해결할 수 있어.
4.2 최적화 예시들
메모이제이션을 사용한 재귀 알고리즘의 최적화 예시들
예시 1: 피보나치 수열
메모이제이션 없이 피보나치 수열을 계산하는 재귀 알고리즘은 시간 복잡도가 지수적이야. 메모이제이션을 사용하면 성능이 크게 개선돼.
def fibonacci(n, memo=None):
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
return memo[n]
# 사용 예시:
print(fibonacci(10)) # 출력: 55
중요! 우리는 memo=None을 기본값으로 사용하고, memo가 전달되지 않았을 때 함수 내에서 빈 사전을 생성해. 이렇게 하면 변경 가능한 객체를 기본값으로 사용하는 문제를 피할 수 있어.
예시 2: 부분집합 합 계산
주어진 집합의 부분집합 중 주어진 값과 합이 같은 것이 존재하는지 확인해야 해.
def is_subset_sum(arr, n, sum_value, memo=None):
if memo is None:
memo = {}
if (n, sum_value) in memo:
return memo[(n, sum_value)]
if sum_value == 0:
return True
if n == 0 and sum_value != 0:
return False
if arr[n - 1] > sum_value:
memo[(n, sum_value)] = is_subset_sum(arr, n - 1, sum_value, memo)
return memo[(n, sum_value)]
memo[(n, sum_value)] = is_subset_sum(arr, n - 1, sum_value, memo) or is_subset_sum(arr, n - 1, sum_value - arr[n - 1], memo)
return memo[(n, sum_value)]
# 사용 예시:
arr = [3, 34, 4, 12, 5, 2]
sum_value = 9
n = len(arr)
print(is_subset_sum(arr, n, sum_value)) # 출력: True
메모이제이션은 사실상 하위 문제의 결과를 캐싱하는 거야.
예를 들어, 피보나치 수 F(10) == F(9) + F(8), 근데 F(9)를 계산하려면 F(8)과 F(7)을 계산해야 해. 그러니까 F(8)은 두 번 계산해야 해: F(9)의 첫 번째 항으로 그리고 F(10)의 두 번째 항으로. 두 번 계산하지 않으려면 첫 번째 계산 후에 캐싱해야 해.
GO TO FULL VERSION