Algorithm Study (DP 동적계획법)

이전내용 링크

 

완전탐색

정렬

문자열

배열,리스트

스택, 큐

해시

힙

DFS, BFS

 

 

14. 동적 계획법

학교에서 알고리즘 수업때만해도 동적프로그래밍이라고 불렀다...

최적화 문제를 연구하는 수학 이론에서 왔으며, 전산학에서 사용하는 동적(Dynamic), 프로그래밍(Programming)과는 아무 관련이 없다고 한다.

따라서 Dynamic Progarmming을 동적 계획법이라고 번역한다.

 

큰 의미에서 분할 정복과 같은 접근 방식을 사용한다.

분할 정복과의 큰 차이점은 문제를 나눌때 DP에서는 부분문제가 두개 이상의 문제를 푸는데 사용된다.

여러번 계산이 필요한 부분을 부분문제로 나누어 이 문제의 답을 재활용하여 속도의 향상을 꾀한다.

이때, 문제의 답을 메모리에 저장하고 이 저장 장소를 캐시라고 부른다.

 

예) 피보나치 계산

 

피보나치 수열을 계산하는 함수를 아래와 같이 작성한다.

이때 fib(5)를 구한다면 계산은 다음과 같이 이루어진다.

 

계산 과정의 3에서 fib(2)의 중복 계산이 이루어지고, 해당 알고리즘의 시간 복잡도는 지수 함수가 된다.

 

각 함수의 계산값을 저장하는 객체 m을 추가하면 이 알고리즘은 다음과 같이 변한다.

이렇게 알고리즘을 변환 하면 시간복잡도는 O(n)이 된다.

 

 

이처럼 두번이상 계산되는 경우를 메모리에 저장하는 방식을 메모이제이션이라고 부른다.

메모이 제이션은 참조적 투명성(입력에 따라 결과가 같은 경우)이 보장되는 함수에만 적용할 수 있다.

 

 

 

출처

위키백과 동적 계획법