반응형 2017/06/061 [알고리즘] 동적 계획법(Dynamic Programming) - 1 동적 계획법(Dynamic Programming) 우리가 전에 피보나치 수를 계산하기 위해 재귀 함수를 사용했었다.이는 같은 연산이 반복되기 때문이다. 그러나 이 함수의 진행 과정을 살펴보면 중복이 심하다는 것을 알수 있다. 위의 그림에서 보면 fib(2)가 여러번 반복되며 오버헤드가 증가함으로 결국 비효율적인 코드가 된다. 따라서 이러한 중복을 제거 하기 위해서 메모이제이션(Memoization)이라는 테크닉을 사용한다.이는 사전에는 나오지 않는 프로그래밍 테크닉이며, 계산된 값을 버리지 말고 저장한다는 뜻이다예를 들어 위의 그림에서 계산이 된 fib(2) 값을 저장해 놓고 있다가, 필요한 경우 계산없이 호출하게 된다.이렇게 저장되는 배열을 '캐시'라고 하며, 중간에 저장하는 걸 '캐싱한다'라고 부른다.. 2017. 6. 6. 이전 1 다음 반응형