본문으로 건너뛰기

메모화로 재귀 함수의 효율성 높이기

메모화로 재귀 함수의 효율성 높이기

재귀 함수는 자기 자신을 호출하는 함수입니다.

하지만 이러한 접근법은 특정 조건에서 비효율적일 수 있으며, 이를 해결하기 위해 '메모화(memoization)' 기법이 사용됩니다.


메모화란?

메모화는 재귀 함수에서 동일한 계산을 반복하지 않도록 이전 계산 결과를 저장하는 기술입니다. 메모화는 특히 복잡한 계산에서 성능을 크게 향상시킵니다.

메모화를 사용한 피보나치 수열 예시
def fibonacci(n, memo={}):
if n in memo: # 이미 계산한 값이라면
return memo[n] # 저장된 값을 반환
if n <= 1: # 종료 조건
return n # 0 또는 1 반환
memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo) # 계산 결과 저장
return memo[n] # 저장된 값 반환

print(fibonacci(10)) # 55

메모화는 중복 계산을 제거하여 프로그램의 실행 속도를 높입니다.


유의사항

  • 메모화를 사용하는 경우 추가 메모리가 필요합니다.

  • 모든 재귀 함수가 메모화를 필요로 하는 것은 아니며, 사용 여부는 함수의 특성과 요구 사항에 따라 결정해야 합니다.

다음 내용이 궁금하다면?

월 12,500원 PLUS 멤버십 가입 or 강의를 등록해 주세요!