[알고리즘] 11/16 이론

DP Algorithm(동적 계획 알고리즘) Dynamic Programming

 

 입력 크기가 작은 부분 문제들을 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여 최종적으로 원래 주어진 입력의 문제를 해결한다.

 

분할 정복 알고리즘과 DP

전형적인 부분 문제들 사이의 관계

 

DP는 부분 문제들 사이에 의존적 관계가 존재한다.

 

작은 부분 문제의 해가 보다 큰 부분 문제를 해결하는데 사용하는 관계가 있다.

 

분할 정복 알고리즘은 부분 문제의 해를 중복 사용하지 않는다.

 

막대 자르기 문제

 막대 길이는 n(양의 정수)이다.

 막대는 길이가 양의 정수로 자를 수 있다. (n-1을 초과할 수는 없다.)

 

 길이가 i인 막대의 판매 가격은 pi 이다.

 길이가 n인 막대를 여러 개의 조각으로 잘라서 판매할 수 있을 때 얻을 수 있는 최대 판매 금액을 구해야한다. 물론 통째로 자르지 않고 팔 수도 있다.

 자르는 경우의 수를 모두 확인해서 최대값을 골라보자.

 

아이디어 :

 먼저 길이가 n인 막대를 처음에 길이 i(1<=i<=n-1)인 막대와 길이가 n-i인 막대로 자른다. 길이가 i인 막대는 그대로 팔고 길이 n-i인 막대는 최대 판매 금액을 얻을 수 있도록 잘라 팔거나, 통째로 판다.

 

길이가 n인 막대를 판매할 때 얻을 수 있는 최대 판매 금액을 R(n)이라고하면,

 R(n) = MAX(pi + R(n-i))

 

이 과정을 재귀를 이용해서 i 만큼 자르고, 나머지 길이의 막대 판매 금액을 구할 수 있다. 그렇게 되면~

 이와 같이 재귀를 실행하게 된다. 중복되는 결과값이 많다! 길이 4를 자르는 데에도 함수 호출이 정말 많다. 지수 시간 알고리즘이다.. 이렇게 같은 함수의 결과를 굳이 확인하는 것은 너무 시간 손해이다.

 

 그렇다면, 기억을 해두면 똑같은 과정을 줄일 수 있지 않을까?

 

DP를 이용한다면 시간복잡도가 지수에서 n^2으로 변하게 된다.

 

모든 쌍 최단 경로 문제