메모이제이션 (Memoization)
메모이제이션 (Memoization) 메모이제이션은 “기억하다"라는 뜻의 라틴어 ‘memorandum’에서 유래했다. 이 기법은 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장해두고 필요할 때 다시 계산하지 않고 저장된 값을 사용하는 방식이다. 실생활에 비유해보면, 책을 보다가 모르는 단어를 사전에서 찾았을 때 메모이제이션 미사용: 같은 단어가 나올 때마다 매번 사전을 찾음 메모이제이션 사용: 찾은 단어의 의미를 메모장에 적어두고, 다시 나오면 메모장을 참고 로 이해 가능하다. 메모이제이션의 작동 원리 함수가 호출될 때 입력값을 확인한다. 해당 입력값에 대한 결과가 이미 저장되어 있다면, 저장된 결과를 즉시 반환한다. 저장된 결과가 없다면, 함수를 실행하고 그 결과를 저장한 후 반환한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 def memoized_function(n, memo={}): # 1. 이미 계산된 값인지 확인 if n in memo: return memo[n] # 2. 새로운 값 계산 result = ... # 계산 로직 # 3. 계산된 값을 저장 memo[n] = result # 4. 결과 반환 return result 메모이제이션의 장점 실행 속도 향상: 중복 계산을 피함으로써 프로그램의 실행 속도를 크게 높일 수 있다. 자원 효율성: 계산 비용이 높은 작업의 결과를 재사용함으로써 컴퓨터 자원을 효율적으로 사용할 수 있다. 메모이제이션의 사용 예시 가장 대표적인 예시로 피보나치 수열 계산을 들 수 있다. 일반적인 재귀 함수로 구현하면 중복 계산이 많이 발생하지만, 메모이제이션을 적용하면 성능을 크게 개선할 수 있다. ...