💾 memoization

오늘 배울 것

• 재귀와 분할 정복
• 메모이제이션
• 문제해결을 위한 고려사항

Memoization

분할된 서브문제를 해결하기 위해, 반복되는 해결법을 재사용하는 기법
(Dynamic Programming에서 활용됨)

• 미리 계산한 값을 재사용하기 때문에 프로그램 실행 속도가 빨라짐
• 함수의 시간 복잡도를 감소시키고, 공간 복잡도를 증가시킴
• 방법: 반복되는 계산 결과를 특정 변수에 저장한다
  
• 'getting memo'로 계산 결과 저장
• 같은 함수에 대해서 'calling function'을 활용하여 재사용

# 메모이제이션 적용되지 않은 경우

def recursive_factorial(n): # 최상위 호출
    if n is 0:
        return 1
    else:
        return n * recursive_factorial(n - 1) # 함수 내부

• 최상위 호출에서 전체 메모리 계산을 진행한다
• recursive_factorial(3)인 경우 호출순서
  1. factorial(3) 호출
  2. factorial(3) 수행이후 factorial(2) 호출
  3. 메모이제이션을 활용하지 않은 경우, factorial(3), factorial(2) 두 함수 모두 factorial(2) 로직을 계산함
     (파라미터의 숫자가 증가할수록 동일한 로직에 대한 계산수 증가)

memo = {} # 계산 결과 저장할 딕셔너리

def factorial(n):
	if n == 0:
    	return 1
    elif n in memo: # 재귀 함수 계산하면서 저장됐다면
    	return memo[n]
    else:
    	result = n * factorial(n-1)
        memo[n] = result # 메모장에 계산한 n, 계산 결과 저장
        return result

이렇게 하면 factorial(5)하고 factorial(4)할 때, 4 값은 24로 memo에 저장해 놨기 때문에 두번째 factorial 함수 호출에서는 로직 계산 필요없이 바로 결과를 출력할 수 있다.