메모이제이션

메모이제이션 (Memoization)은 컴퓨터 프로그래밍에서 동일한 입력에 대해 함수 또는 메서드의 결과를 저장하여 이후 동일한 입력이 발생했을 때 다시 계산하지 않고 저장된 결과를 즉시 반환하는 최적화 기법이다. 동적 프로그래밍의 핵심적인 부분으로, 주로 재귀 함수나 반복적인 계산이 많은 알고리즘의 성능을 향상시키는 데 사용된다.

개념 및 작동 방식

메모이제이션은 함수의 결과를 저장하기 위한 자료 구조(일반적으로 캐시 또는 딕셔너리)를 활용한다. 함수의 실행 과정은 다음과 같다.

함수가 특정 입력 값으로 호출되면, 먼저 캐시를 확인하여 해당 입력 값에 대한 결과가 이미 저장되어 있는지 확인한다.
만약 캐시에 저장된 결과가 있다면, 그 결과를 즉시 반환한다.
만약 캐시에 저장된 결과가 없다면, 함수는 계산을 수행하고 결과를 캐시에 저장한 후 반환한다.

이러한 과정을 통해 동일한 입력에 대한 중복 계산을 피하고, 프로그램의 실행 시간을 단축시킬 수 있다.

장점 및 단점

장점:

성능 향상: 동일한 입력에 대한 중복 계산을 제거하여 실행 시간을 단축시킨다. 특히, 재귀 함수의 경우 성능 향상 효과가 크다.
자원 절약: 중복 계산을 줄임으로써 CPU 사용량 및 메모리 사용량을 절약할 수 있다.

단점:

추가적인 메모리 사용: 함수의 결과를 저장하기 위한 캐시 공간이 필요하므로, 메모리 사용량이 증가할 수 있다.
캐시 관리의 복잡성: 캐시의 크기를 제한하거나, 캐시된 데이터를 업데이트 또는 삭제하는 등의 캐시 관리 로직이 필요할 수 있다.
적용 가능성의 제한: 함수의 입력 값이 복잡하거나, 입력 값의 범위가 매우 넓은 경우에는 메모이제이션의 효과가 미미할 수 있다. 또한, 함수의 부작용(Side Effect)이 있는 경우 메모이제이션을 적용하기 어렵다.

활용 예시

피보나치 수열: 재귀적으로 피보나치 수열을 계산하는 함수에 메모이제이션을 적용하여 성능을 크게 향상시킬 수 있다.
조합 계산: 조합 (Combination) 또는 순열 (Permutation) 계산과 같이 중복 계산이 많은 경우 메모이제이션을 통해 효율적인 계산이 가능하다.
그래프 탐색: 다익스트라 알고리즘 (Dijkstra Algorithm) 또는 A* 알고리즘 (A* Algorithm)과 같이 그래프 탐색 알고리즘에서 이미 방문한 노드에 대한 정보를 저장하여 중복 탐색을 방지하는 데 활용될 수 있다.

관련 용어

동적 프로그래밍 (Dynamic Programming): 복잡한 문제를 작은 부분 문제로 나누어 해결하고, 부분 문제의 결과를 저장하여 재사용하는 알고리즘 설계 기법. 메모이제이션은 동적 프로그래밍의 핵심적인 요소이다.
캐싱 (Caching): 자주 사용되는 데이터나 결과를 임시 저장 공간에 저장하여 이후 접근 속도를 향상시키는 기술. 메모이제이션은 캐싱의 한 형태로 볼 수 있다.