메모화로 재귀 함수의 효율성 높이기
재귀 함수는 자기 자신을 호출하는 함수로, 같은 계산을 반복하게 되어 성능이 저하될 수 있습니다.
이러한 문제점을 해결하기 위해 메모화(Memoization) 기법이 사용됩니다.
메모화란?
메모화는 함수의 반환 값을 저장해 두었다가, 같은 입력에 대해 함수를 다시 호출할 때 저장된 값을 반환하는 기법입니다.
메모화를 사용하면 함수의 반환 값을 저장해 두어 중복 계산을 방지하고, 함수의 실행 속도를 높일 수 있습니다.
메모화를 사용한 피보나치 수열 예시
def fibonacci(n):
# 메모이제이션에 사용할 빈 딕셔너리 생성
memo = {}
def helper(x):
# 이미 계산된 값이 있으면 저장된 값을 반환
if x in memo:
return memo[x]
# 종료 조건: 0 또는 1일 때 x 반환
if x <= 1:
return x
# 계산 결과를 메모이제이션 딕셔너리에 저장
memo[x] = helper(x - 1) + helper(x - 2)
return memo[x]
# 재귀 함수 호출
return helper(n)
# 10번째 피보나치 수열 값 출력
print(fibonacci(10))
# 55
위 코드에서 memo 딕셔너리를 사용해 이전에 계산한 값을 저장하고, 이미 계산한 값이라면 저장된 값을 반환합니다.
딕셔너리에 담기는 값은 아래와 같은 n에 대한 피보나치 수열의 결과입니다.
memo 딕셔너리
{
2: 1,
3: 2,
4: 3,
5: 5,
6: 8,
7: 13,
8: 21,
9: 34,
10: 55
}
메모화를 사용하면 함수의 실행 속도를 높일 수 있으며, 중복 계산을 방지해 성능을 향상시킬 수 있습니다.
하지만 계산 결과를 저장해 두기 위한 추가적인 메모리가 필요하므로, 메모화를 사용할 때는 메모리 사용량에 주의해야 합니다.
다음 내용이 궁금하다면?
코드프렌즈 PLUS 멤버십 가입 or 강의를 등록해 주세요!