메모이제이션

구조

1) 초기화

2) 기저 사례 처리

3) 이미 처리한 값인지 확인(초깃값인지 확인)

4) 계산

 

시간 복잡도 : 부분 문제의 수 * 부분 문제를 처리하는데 걸리는 시간

 

메모이제이션을 위해서는 *참조적 투명성* 필요.

함수의 입력값에만 의해서 값이 결정됨.

전역 변수 등의 영향을 받지 않음

 

비둘기 집의 원리

- 경로는 무수히 많을 수 있지만, 입력의 수는 경로보다 적은 경우, 메모이제이션이 유용할 수 있음

 

배열의 크기를 하나 더 키워서

첫번째 인덱스를 -1이나 0을 넣어서 예외상황/초깃값 처리를 쉽게 할 수 있다.

 

관련 문제 : 가장 긴 부분 증가 수열(구종만 p.234 nlog n 해법 다시 공부하기)