DP 동적 계획법

<포인트>

1. 큰 문제를 작은 문제들로 나누어 해결한다

2. 작은 문제들은 결과값을 저장하여 다시 사용할 수 있도록 한다 ( 메모이제이션 )

 

<차별점>

주로 greedy(그리디, 탐욕)알고리즘과 자주 비교된다.

(공통)

둘다 전체 문제를 작은 문제단위부터 해결하여 최적점에 도달한다는 전략을 취하지만,

(차이)

greedy는 작은 문제단위에서 최선의 선택이 큰 문제에서의 최선의 선택과 일치되는 경우에 사용 가능하고,

dp는 작은 문제단위에서 best선택을 하더라도 큰 문제에서 best가 보장되지 않을 때 사용하면 된다.

 

<풀이방법>

1. Top-Down 방식

 : 초기의 큰 문제단위에서 작은 문제단위로 접근하며

 : 재귀함수를 이용해 구현한다

 1) 작은 문제들의 결과값을 저장할 변수를 만들고 모두 worst상태로 초기화한다

 2) function 앞부분에 return 조건을 마련한다 (-> 작은 문제단위에서 결과값 도출 조건 )

 3) 인자로 작은 문제단위를 넘겨주고 function을 부르면서 worst와 비교 후 업데이트

 

2. Bottom-Up 방식 

 : 가장 작은 문제단위부터 초기 문제단위로 넓혀가며

 : for문을 이용해 구현한다

 1) 1.과 똑같이 메모이제이션에 활용할 변수를 만들고 모두 초기값으로 setting한다

 2) (이전 스텝과 무관한 방안도 있다면) for문 앞부분에 현재상태를 업데이트하도록 한다

 3) 저장된 이전 스텝의 결과값을 이용 또는 비교하여 현재 스텝의 최적점을 업데이트한다

 

* 메모리나 속도면에 있어서 Bottom-up방식이 유리하므로, for문으로 문제를 해결하는 습관을 들이자

 

<대표방식>

1. n번쨰로 도달할 방법은 n-1번쨰에서와 n-2번째에서 결정되는 경우

주로 결과점까지의 도달방법이 두가지일 경우 도달방법의 개수를 구할 때 다음의 해결법이 사용할 수 있다

좌우 순서에 구애받지 않을 경우는 S(n) = S(n-1) + S(n-2)

ex. 피보나치수열, BOJ_11726 2n 타일링

 

2. 최적점 찾기 (그리드방법과 다르다 -> 그리드의 경우 작은 문제에서 항상 베스트 선택을 고르면 끝)

어떤 작은 문제들의 조합이 최적점에 도달할지 모르기 때문에

도달점 이전의 모든 값의 경우를 체크하고 업데이트 해야한다

특히 이 경우, 재귀로 이를 풀게되면 메모리 에러에 도달할 수 있다.

python의 경우 recursion 한도를 정해두기 때문에 sys.setrecursionlimit()로 에러를 제어해야 한다.