종만북 8장 [w/ Python]

동적 계획법( dynamic programming) 

 

- 문제를 잘게 쪼개 해결해 나가는 과정에서 반복되는 부분을 캐시에 저장하여 재사용하는 기법

 

- 분할정복과 문제를 작게 쪼깬다는 측면에서 공통점이 있지만 분할정복의 경우 부분문제들이 겹치지 않아 부분문제를 합병해 나가는 과정을 거치고 동적계획법은 반복되는 부분문제의 재연산을 피하기위해 캐시에 저장하는 메모이제이션(memoization)기법을 사용한다.

 

- 참조적 투명성(referential transparency) : 함수의 반환 값이 그 입력 값만으로 결정되는지의 여부(전역변수, 입력 파일 등 함수 외부 요인에 의해 영향을 받지 않는 함수)

 

- 메모이제이션은 참조적 투명 함수의 경우에만 적용할 수 있다. 입력이 같은데 외부 요소에 따라 다른 갑싱 반환되면 캐싱을 할 수 없기 때문이다.

 

메모이제이션의 시간 복잡도 분석 

 

- 메모이제이션의 경우 처음 함수를 호출할 때와 그 이후 호출할 때 걸리는 시간이 다르기 때문에 시간복잡도를 계산하기가 어렵다. 그래서 다음 식을 이용하는것이 좋다.

 

(존재하는 부분 문제의 수) * (한 부분 문제를 풀 때 필요한 반복문의 수행 횟수)

 

예) 이항계수(binomial coefficient) 을 계산할 때 r의 최대치는 n이므로 만날 수 있는 부분문제의 최대 개수는 O(n^2)가 되고, 각 부분문제에서 반복문은 존재하지 않으므로 O(1)이 되어 bino()의 시간복잡도는 O(n^2)*O(1) = O(n^2)가 된다.

 

동적 계획법 레시피

 

1. 주어진 문제를 완전 탐색을 이용해 해결한다.

2. 중복된 부분 문제를 한 번만 계산하도록 메모이제이션을 적용한다.

 

 

 

 

출처 : 프로그래밍 대회에서 배우는 알고리즘 문제해결전략