메모이제이션(Memoization)

 

 

분할된 서브문제를 해결하기 위해, 반복되는 해결법을 재사용하는 기법

미리 계산한 값을 재사용하므로 프로그램 실행속도를 빠르게 해준다

방법 : 반복되는 계산 결과를 특정 변수에 저장

 

################################
memoization을 사용하지 않은 재귀의 경우
################################

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

print(recursive_factorial(10))
print(recursive_factorial(4))

# 해석
n=5 를 호출, 수행한 뒤 n=4를 호출할때
factorial(5)와 factorial(4) 함수를 호출하고, 두 함수 모두 factorial(4) 로직을 계산하게 된다
################################
memoization을 활용한 경우
################################

memo = {}    # 재사용을 값을 저장하기 위한 딕셔너리 변수

def recursive_factorial(n):
    if n is 0:
        return 1
    elif n in memo:
        return memo[n]   # 메모이제이션
    else:
        result = n * recursive_factorial(n - 1)
        memo[n] = result
        return result

# 1번째 케이스
print("recursive_factorial(5):",recursive_factorial(5)," memo:", memo)

# 2번째 케이스
print("recursive_factorial(4):",recursive_factorial(4)," memo:", memo)