코딩 테스트에서 재귀 알고리즘의 성능을 최적화하기 위해서 자주 사용되는 메모이제이션 (Memoization)에 대해서 알아봅시다.
캐싱이란?
먼저 프로그래밍 입문자 분들을 위해서 캐싱에 대해서 간단히 개념은 짚고 넘어가는 게 좋을 것 같습니다. 일반적으로 캐싱은 접근하는데 시간이 오래 걸리는 데이터를 접근 속도가 빠른 저장소에 사본을 저장해두고 재사용하거나, 실행하는데 오래 걸리는 연산의 결과를 미리 계산해놓고 최초로 필요할 때 한번만 계산하여 저장해놓고 재사용하는 기법을 의미합니다.
예를 들어, 대부분의 웹브라우저는 클라이언트 컴퓨터에 캐시를 두고 있는데요. 이 캐시에 이 전에 방문했던 웹페이지의 내용을 저장해놓고 동일한 페이지를 재방문 시 이 저장해놓은 사본의 페이지를 보여주는 경우가 많습니다. 이렇게 함으로써 불필요한 HTTP 통신을 줄이고, 좀 더 기민한 웹 브라우징 경험을 제공할 수 있는 것이지요. 캐싱은 서버 단에서도 성능 최적화를 위한 핵심 도구로 사용되고 있습니다. 예를 들어, 클라이언트로 부터 받은 요청에 대한 처리 결과를 캐시에 저장두고, 나중에 동일한 요청이 들어왔을 때 저장해둔 결과를 그대로 응답하는 것은 매우 흔한 서버 단의 캐싱 패턴입니다.
뿐만 아니라 캐싱은 데이터베이스와 같은 핵심적인 서버 자원을 과부하로 부터 보호하기 위해서도 사용할 수 있습니다. 애플리케이션에서 데이터베이스로 부터 불러온 데이터를 캐시에 저장해놓고 재사용해준다면 중복 쿼리가 줄어 데이터베이스 입장에서 동시에 처리해야하는 부담이 현저히 줄어들 것입니다.
하드웨어 쪽에서는 캐싱이 고성능 저장 매체와 저성능 저장 매체 사이의 속도 차이로 인한 성능 손실을 최소화 하기 위해서 많이 사용됩니다. 대표적인 예로, CPU와 RAM 사이에 있는 CPU 캐시를 들 수 있는데요. 하드 디스크(HDD, SSD)의 일부 용량을 마치 메모리처럼 사용하는 가상 메모리 전략도 비슷한 맥략으로 볼 수가 있겠습니다.
네트워크 쪽에서는 프록시(Proxy) 서버나 CDN(Content Delivery Network)을 대표적인 캐싱 사례로 들 수 있겠네요. 유저와 최대한 가까운 CDN 노드(node)에 이미지나 비디오 같이 고용량 데이터의 사본을 저장해놓으면, 굳이 지리적으로 멀리 있는 서버로 부터 원본 데이터를 다운로드를 받을 필요가 없을 것입니다.
메모이제이션이란?
메모이제이션(memoization)은 시간이 오래 걸리는 함수의 호출의 결과를 저장해두었다가 동일한 입력으로 해당 함수가 다시 호출 될 때 저장해둔 결과를 반환하여 애플리케이션 속도를 높이는 기술입니다. 메모이제이션은 가장 원초적인 형태의 캐싱으로서 저장 공간에 별도의 상한선을 두지 않는 캐싱 방법입니다.
저장 공간에 별도의 상한선을 두지 않는다는 것은 이론적으로 캐시가 차지하는 크기가 무제한으로 늘어날 수 있는 말인데요. 일반적으로 캐싱을 위해 사용되는 저장 매체는 접근 속도가 빨라야 하므로 가격이 자연스럽게 비싸질 수 밖에 없습니다. 그러므로 실제로 소프트웨어 제품을 개발할 때는 메모이제이션을 쓸 수 있는 경우는 극히 제한적일 것입니다.
하지만 저장 공간에 별도의 상한선이 없다는 것은 그만큼 간단하게 구현할 수 있다는 뜻이기 때문에 코딩 테스트에서는 캐싱을 위해서 메모이제이션을 매우 흔하게 사용됩니다. 특히 재귀 알고리즘에서 불필요한 중복 계산을 제거하고 싶을 때 메모이제이션이 큰 힘을 발휘합니다.
메모이제이션 구현
메모이제이션을 구현할 때는 일반적으로 해시 테이블 자료구조를 사용하여 함수의 첫 번째 호출 결과를 저장해놓고 두 번째 호출부터는 기존에 저장된 결과를 재사용합니다.
아래 do_with_memoization() 함수를 보시면, 인자로 넘어온 key가 캐시에 존재하지 않을 때만 do_something() 함수를 호출하여 결과를 캐시에 저장한 후 반환합니다.
이를 통해서, 다음에 동일한 key가 인자로 넘어오면 캐시에 저장해놓은 값을 읽어서 반환할 수 있습니다.
cache = {}
def do_with_memoization(key):
if key not in cache:
cache[key] = do_something(key)
return cache[key]
def do_something(key):
pass # 시간이 오래 걸리는 작업보통 어떤 키에 대한 값이 아직 캐시에 저장되이 않은 상황을 cache miss라고 하고, 캐시에 이미 값이 저장되어 있는 상황을 cache hit라고 하는데요.
do_with_memoization() 함수를 동일한 인자로 여러 번 호출하면, 최초에는 cache miss가 되고, 그 이후부터는 cache hit가 될 것입니다.
do_with_memoization(1) # cache miss
do_with_memoization(1) # cache hit
do_with_memoization(1) # cache hit동일한 인자로 do_with_memoization() 함수를 반복해서 호출해야하는 경우, 메모이제이션을 통해 크게 실행 시간을 단축시킬 수 있습니다.
코딩 테스트에서 활용
코딩 테스트에서 메모이제이션은 재귀 알고리즘의 시간 복잡도를 낮추기 위해서 자주 활용되는데요. 재귀 알고리즘에서 흔하게 발생하는 중복 계산을 메모이제이션으로 제거하면 성능을 비약적으로 향상시킬 수 있습니다.
재귀 알고리즘으로 플 수 있는 아주 유명한 문제인 피보나치 (Fibonacci) 수열의 경우,
메모이제이션을 해주지 않으면 엄청난 양의 중복 계산이 발생하고, 그에 따라 시간 복잡도가 O(2^N)으로 매우 비효율적입니다.
예를 들어, fib(5)를 구하려면 fib(3)는 두 번, fib(2)는 세 번, fib(1)은 무려 다섯 번이나 반복해서 계산해야합니다.
fib(5) => 3 + 2 = 5
fib(4) => 2 + 1 = 3
fib(3) => 1 + 1 = 2
fib(2) => 1 + 0 = 1
fib(1) => 1
fib(0) => 0
fib(1) => 1
fib(2) => 1 + 0 = 1
fib(1) => 1
fib(0) => 0
fib(3) => 1 + 1 = 2
fib(2) => 1 + 0 = 1
fib(1) => 1
fib(0) => 0
fib(1) => 1하지만 메모이제이션을 적용할 경우, fib(3), fib(2), fib(1)이 모두 한 번만 계산해도 됩니다.
중복 계산이 모두 제거되기 때문에 시간 복잡도가 O(n)으로 비약적으로 향상됩니다.
fib(5) => 3 + 2 = 5
fib(4) => 2 + 1 = 3
fib(3) => 1 + 1 = 2
fib(2) => 1 + 0 = 1
fib(1) => 1
fib(0) => 0
fib(1) => ✅ cache hit
fib(2) => ✅ cache hit
fib(1) => ✅ cache hit
fib(0) => ✅ cache hit
fib(3) => ✅ cache hit
fib(2) => ✅ cache hit
fib(1) => ✅ cache hit
fib(0) => ✅ cache hit
fib(1) => ✅ cache hit메모이제이션의 단점
메모이제이션을 하려면 계산 결과를 저장해놓아야하므로 추가적인 메모리가 필요하기 마련입니다.
보통 입력 데이터의 크기만큼, 즉 O(n)의 공간 복잡도를 요구하게 됩니다.
하지만 시간 복잡도 측면에서 얻는 성능적인 이득이, 공간 복잡도 측면에서 잃는 손해를 감수하고도 남는 경우가 대부분입니다.
또한 메모이제이션을 사용 시, 캐시에 결과를 저장하고 읽어오는 부분 때문에 코드가 상대적으로 읽기 어려워지는 경향이 있습니다. 다행이도 파이썬과 같은 일부 프로그래밍 언어에서는 자체적으로 메모이제이션 기능을 제공하는데요. 이러한 기능을 활용하면 코드 가독성을 크게 해지지 않으면서도 메모이제이션을 적용할 수 있을 것입니다.
추천 문제
메모이제이션 기법을 연습하시는데 아래 문제를 추천드리겠습니다.