[python/Memoization] 파이썬으로 여러 방법으로 피보나치 수열 풀어보기(Memoization in python)

코드워즈로 공부를 하고 있는데, 메모이제이션을 통해 피보나치 수열을 계산하는 함수의 효율을 개선하는 문제를 풀게되었다.

 

여러분도 풀어보세요!

 

---

 

kata 분석하기

def fibonacci(n):
    if n in [0, 1]:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

문제에서는 n이 0에 도달할 때까지 재귀함수 형태로 반복해서 fibonacci 함수를 호출하고 있다. 정상적으로 작동하는 함수이지만, 이 형태 그대로 함수를 돌리게 되면 fibonacci(0)과 fibonacci(1)이 엄청나게 많이 메모리에 쌓이게 된다. 같은 값임에도 불구하고 다르게 처리해야하는 비효율성이 생긴다. 때문에 메모리에 부담도 많이가고, 시간도 엄청 오래걸리게 된다. 

그렇다면 이 문제는 어떻게 풀 수 있을까?

fibonacci(0)과 fibonacci(1)을 미리 메모리값에 저장해두고, 불필요한 연산들은 줄여보자.

피보나치 수열에 대한 부분은 여기서 확인해보세용~!

 

이럴 때 메모리에 값을 저장하고 호출하는 것이 Memoization(메모이제이션)이다.

그리고 메모이제이션은 동적계획법의 일부라고 한다.

 

 

동적계획법과 메모이제이션

 

• 동적계획법: 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법,  최단 경로 문제, 행렬의 제곱 문제 등의 최적화에 사용된다. 이것은 동적 계획법은 문제를 해결하기 위한 모든 방법을 검토하고, 그 중에 최적의 풀이법을 찾아내기 때문이다.
  
  
• 메모이제이션: 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술

 

메모이제이션 ⊂ 동적계획법(Dynamic Programming)

 

 

Memoization in Python

 

dictionary 사용하기

 

말그대로 필요한 값을 딕셔너리에 저장한 후, 호출하여 사용해보자!

fib_memo = {}
def fibonacci(n):
    if n in fib_memo:
        return fib_memo[n]
    else:
        fib_memo[n] = n if n < 2 else fibonacci(n-2) + fibonacci(n-1)
        return fib_memo[n]

# 번외: 리스트도 쓸 수 있지 않을까?
def fibonacci(n):
    """
        - len(x) = n+1 인 list x를 만든다.
        - x[0]=0, x[1]=1 로 지정
        - x[n] = x[n-2] + x[n-1] (n>=2)
        - 사실 dict와 다른 것이 전혀 없다. dict에서의 key역할을 리스트에서는 index가 대체한다.
    """
    x = [i for i in range(n+1)]
    for idx in range(2, n+1):
        x[idx] = x[idx-2] + x[idx-1]
    return x[n]

 

 

functools.lru_cache() 사용하기

 

l(L)ru_cache의 lru는 뭘까? Least Recently Used를 의미한다. 해당 함수를 사용하면 과거 사용했던 함수의 리턴 결과를 캐시할 수 있다. 데코레이터 형태로 사용한다. 예를 들어 func()라는 함수를 인자를 다르게 담아 호출한다고 해보자.

호출 순서	func(1)	func(2)	func(3)	func(2)	func(1)	func(4)	func(3)
메모리 저장 여부	O	O	O	X(기존 캐시 사용)	X(기존 캐시 사용)	O	X(기존 캐시 사용)
캐싱 여부	X(최초호출)	X(최초호출)	X(최초호출)	O	O	X(최초호출)	O

위의 이미지처럼 2번 이상 호출하는 경우 메모리에서 값을 가져오는 형태이다.

functools.lru_cache()는 함수의 리턴 결과를 캐시해주며 보통 데코레이터 형태로 사용한다. 인자값으로 maxsize를 넣을 수 있으며, 캐시항목이 maxsize를 넘어가는 경우에는 호출빈도가 가장 낮은 것부터 캐시에서 삭제한다. 만약 위의 테이블에서 @functools.lru_cache(maxsize=2)를 설정했다면, func(1)과 func(2) 까지만 저장되고, func(3)이 호출되는 순간 func(1)은 지워질 것이다. 때문에 maxsize의 크기를 적절하게 설정하는 것도 프로그래밍의 효율성에 중요한 요소이다.( 숫자가 크면 차지하는 메모리가 커지고, 적다면 값을 반복해서 호출하게될 수 있기 때문) 

이를 이용하여 피보나치 수열을 아래와 같이 풀 수 있다.

from functools import lru_cache

@lru_cache()
def fibonacci(n):
    if n < 2:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(10))
print(fibonacci.cache_info()) # 캐시 정보를 알 수 있다.

 

참고자료

피보나치 수 - 위키백과, 우리 모두의 백과사전

동적 계획법 - 위키백과, 우리 모두의 백과사전

Mastering Memoization in Python

파이썬과 컴퓨터 사이언스(기본 알고리즘): 동적 계획법과 분할 정복 - 잔재미코딩

 

[Python 으로 푸는 Leetcode]146. LRU Cache

functools — 고차 함수와 콜러블 객체에 대한 연산 — Python 3.9.7 문서

 

 

아 이번글은 뭔가 특별한 것은 없지만 뿌듯한데 검색 알고리즘 많이타면 좋겠다 ㅎㅎ