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

혹시 피보나치의 수를 구하는 알고리즘을 알고 계신가요?

아마 많은 분들이 재귀함수를 사용하는 알고리즘을 떠올릴 것입니다.

N = int(input())

def fib(N):
    if N == 0 or N == 1:
        return N
    return fib(N - 1) + fib(N - 2)


print(fib(N))
# input  output  time
# 10     55      0.00092s
# 5      5       0.00018s
# 100            한없이 긴 시간이 소요됩니다...

얼핏 보면 완벽해 보이는 알고리즘이지만 여기에는 함정이 하나 숨어있는데요,

잠깐 5번째 피보나치 수를 구하는 과정을 그림으로 소개하자면 아래와 같습니다.

5번째 피보나치 수는 4번째 피보나치 수와 3번째 피보나치 수를 더한 결과이며, 4번째 피보나치 수는 3번째 + 2번째... 이런 식으로 트리 구조가 형성된 모습입니다. 그런데 트리를 잘 보면 중복된 계산으로 인해 시간과 메모리가 낭비되는 문제를 예상할 수 있습니다.

Q. 낭비돼봐야 얼마나 낭비되겠어요? 어차피 컴퓨터는 우리 생각보다 빠르잖아요?

어, 사실 조금 많이 낭비됩니다.

10번째 피보나치 수를 구할 때는 함수가 100번이 넘게 호출되고, 21번째 피보나치 수를 구할 때는 무려 3만 번이 넘는 호출이 필요합니다.

그리고 100번째 피보나치 수를 구하기 위해서는 정말 긴 시간이 필요합니다. (궁금해서 돌려봤지만, 20분이 넘어도 구할 수 없었습니다.)

메모이제이션

이런 불필요한 재계산을 방지하기 위한 기법이 바로 메모이제이션(memoization) 이라는 기법입니다.

(* 리액트의 복잡한 함수의 실행 결과를 저장해두고 재사용할 수 있는 useMemo 훅도 바로 여기서 따온 이름입니다.)

N = int(input())
memo = [0] * 1000


def fib(N):
    if N == 1 or N == 0:
        memo[N] = N
        return memo[N]
    if memo[N] != 0:
        return memo[N]
    else:
        memo[N] = fib(N - 1) + fib(N - 2)
        return memo[N]


print(fib(N))

메모이제이션의 핵심은 "이전 단계에서 활용했던 값을 재활용하는 것" 이라고 할 수 있는데요, 위 코드를 살펴보면 N번째 피보나치 수를 구한 후 재활용을 위한 배열에 저장합니다. 이후에 계산하는 피보나치 수가 전에 계산했던 값이라면, 배열에 저장된 값을 꺼내와 재활용합니다.

 

그럼 계산 비용이 놀랄만큼 줄어든 것을 확인할 수 있습니다.

어떤가요? 21번째 피보나치 수를 구하기 위해 함수를 약 3만 번 호출하다가 메모이제이션을 적용하니 41번만에 계산을 마칠 수 있었습니다.

 

이처럼 "이전 결과를 재활용한다" 는 컨셉은 동적 계획법 문제를 해결할 때 핵심 아이디어가 되곤 하는데요, 웹 개발 공부를 해보신 분들이라면 브라우저가 캐시를 활용하는 이유와 엮어 생각해보시면 금새 이해하실 수 있을 거라고 생각합니다. 😄