[알고리즘] 메모이제이션(Memoization)

메모이제이션

메모이제이션이란 동일한 계산을 반복할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 실행 속도를 빠르게 하는 기술입니다. 이는 동적 계획법(Dynamic Programming)에서 핵심이 되는 기술입니다. 캐싱이라고 표현되기도 합니다.

 

예를 들어 재귀 함수를 사용한 피보나치 수열 함수가 있다고 해봅시다.

func fibonacci(_ n: Int) -> Int {
    if n <= 0 {
        return 0
    } else if n == 1 {
        return 1
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2)
    }
}

재귀 함수를 사용하게 된다면 반복적으로 fibonacci 함수를 불러오기 때문에 불필요한 연산이 생기고,

실행 속도가 느려질 수 있습니다.

 

따라서 다음과 같이 메모리에 값을 저장하고 해당 값을 불러옴으로써 실행 속도를 빠르게 해줄 수 있습니다.

func fibo(_ n: Int) -> Int {
    var fiboArray: [Int] = [0, 1]
    
    guard n > 1 else { return n }
    
    for num in 2...n {
        fiboArray.append(fiboArray[num - 2] + fiboArray[num - 1])
    }
    
    return fiboArray[n]
}