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

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

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

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

Copy
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

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

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

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