메모이제이션(Memoization) 개념 및 예시, 재귀(recursion)

이번 포스팅에서 다루는 memoization 메모이제이션은 DP 동적 계획법 알고리즘에서 핵심이 되는 기술로 중복 계산을 제거함으로써 프로그램의 전체적인 실행 속도를 빠르게, 성능을 향상할 수 있는 기법입니다. 피보나치수열을 예시로 하여 재귀와 메모이제이션의 구현까지 알아보겠습니다.

 

Memoization 메모이제이션이란?

메모이제이션 memoization

기억되어야 할 것이라는 뜻의 라틴어에서 파생된 단어로, 컴퓨터 프로그램이 동일한 계산을 반복적으로 해야 할 때, 이전에 계산한 값을 메모리에 저장하여 중복적인 계산을 제거하여 전체적인 실행 속도를 빠르게 해주는 기법으로 동적 계획법(DP; Dynamic Programming)의 핵심이 되는 기술입니다.

 

DP Dynamic Programming 동적 계획법 알고리즘과 예제

DP Dynamic Programming 동적 계획법 알고리즘과 예제

 

피보나치수열로 알아보는 재귀(recursion)와 memoization

특히 함수 내에서 자기 자신을 다시 호출하여 작업을 수행하는 재귀 함수를 구현할 때 동일한 계산을 반복해야 할 경우가 많습니다. 그래서 재귀 함수의 대표적인 예제인 피보나치수열 알고리즘을 예시로 memoization을 더 쉽게 알아봅시다.

피보나치수열은 첫째 및 둘째 항이 1이고 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열입니다.

피보나치 수를 구하는 재귀 함수 알고리즘의 문제점은 엄청난 중복 호출이 발생한다는 점입니다.

 

같은 입력값에 대한 함수 호출이 많이 중복되는데 예를 들면

fibo(2)를 구할 때는 fibo(1)을 1번 호출하지만, fibo(4)를 구할 때는 3번, fibo(6)을 구할 때는 8번..

만약 fibo(n)의 n의 수가 훨씬 커진다면, fibo(1)도 엄청난 횟수의 중복 호출을 해야 합니다.

결국 프로그램의 전체적인 실행 속도가 느려질 수밖에 없습니다.

 

이러한 단점을 보완할 수 있는 프로그래밍 기법이 바로 memoization 기법입니다.

피보나치 수를 구하는 알고리즘에서 fibo(n)의 값을 계산하고 저장해 놓으면 다음 계산에서 필요할 때 값만 가져와서 사용하면 되므로 실행 시간을 줄일 수 있습니다.

 

파이썬으로 비교한 재귀 함수와 메모이제이션 알고리즘입니다.

재귀 함수를 사용한 피보나치수열 알고리즘

재귀적 구조로 인한 중복 호출 발생

def fibo(n):
    if n < 2:
        return n
    else:
        return fibo(n - 1) + fibo(n - 2)

 

메모이제이션 기법을 사용한 피보나치수열 알고리즘

메모이제이션 리스트에 값이 저장되어있으면 다시 계산하지 않는 알고리즘

fibo_memo(n)의 결과 값이 memo [n]에 저장됩니다.

def fibo_memo(n):
    global memo
    if n >= len(memo):
        memo.append(fibo(n - 1) + fibo(n - 2))
    return memo[n]

memo = [0, 1]

 

메모이제이션 예제

[BaekJoon] 백준 2748 피보나치 수 2 (Python / 파이썬)

[BaekJoon] 백준 2748 피보나치 수 2 (Python / 파이썬)

---

fibonacci 피보나치수열 알고리즘을 예시로 하여 재귀와 메모이제이션 기법에 대해 알아보았습니다. 다음 포스팅에서는 메모이제이션 동적 계획법의 개념과 활용 예제를 알아보겠습니다.