DP 정복 - 2.3 메모 전략

이번 절은 드디어 '메모 전략'에 대한 소개다.

사실 내용은 크게 많지 않다. 이미 계산한 값을 메모리에 캐시를 해놔서

재귀 호출 내의 함수 호출 횟수를 줄이는 방법이다.

 

메모 전략에서는 어떤 하위 문제를 처음 계산했을 때 그 결과를 일종의 캐시에 저장.

같은 하위 문제를 다시 풀어야 할 때는 이를 완전히 새로 풀지 않고 캐시에서 이미 풀어뒀던 결과를 가져와 반환.

 

피보나치수열 계산의 경우에는 반복 계산하는 케이스보다는 메모 전략이 효율이 떨어지지만,

단순 재귀 호출에 비해서는 엄청난 효율을 갖는다.

 

메모 전략에서는 캐시의 자료형을 결정하는 것이 매우 중요.

캐시는 모든 하위 문제의 결과를 저장하기에 충분해야 함.

일반적으로 배열을 사용하,

문제가 단 하나의 차원으로 구성되면 1차원 배열을 사용, 아니라면 다차원 배열을 사용함.

 

기억해야 할 점

- 메모 전략도 재귀 접근 방법에 속함.

- 재귀 호출에서 발생하는 하위 문제의 반복 계산이라는 부작용을 피하면서도 문제의 구체화 및 하향식 문제 해결이라는 재귀 접근 방식의 이점 살릴 수 있음.

 

메모 전략 = 재귀 호출 + 캐시 - 하위 문제의 반복 계산

- 사실 하위 문제의 반복 계산이 없으면 단순 재귀 호출이나 메모 전략이나 차이가 없음.