[알고리즘] DP (Dynamic Programming)

1 . DP 조건

① . Overlapping Subproblem : 분할된 작은 문제들이 겹치면서 중복된다.

② . Optimal Structure : 분할된 작은 문제의 최적해들을 결합하면 전체 문제의 최적해가 된다.

 

2 . DP 특징

① . DP 는 문제를 작게 나누어 최종 문제를 조건부 점화식을 통해 구현할 수 있을 때 가장 이상적이다.

② . 작은 문제의 답이 중복되지 않는 구조라면 DP 가 비효율적일 수 있다.

③ . 분할정복과 동적계획법은 작은 문제로 분할하여 문제를 해결한다는 점에서 유사하지만, 분할정복은 작은 문제의 답을 활용하지 않는 반면에 동적계획법은 분할된 문제들의 답을 활용한다는 점이다.

 

3 . DP 풀이 방식

DP 를 풀이하는 방법에는 top-down 과 bottom-up 방식이 있다.

① . top-down (Memoization) : 시작 위치에서 마지막 위치로 내려가며 최종 답을 점화식을 통해 먼저 구현하고 중간 중간 작은 문제들의 답을 구해 문제를 푼다. 이 때 중간 작은 문제들의 답은 DP 특성 상 중복되기 때문에 결과 값을 저장하여 바로 로드한다. 보통 재귀와 lookup table 를 사용하며 프로그램 스택을 사용하는 것이 특징이다.

② . bottom-up (Tabulation) : 마지막 위치에서 시작 위치로 올라가며 작은 문제들의 답을 풀어가면서 최종 답을 구한다. 보통 반복문으로 구성된다.

(위 3-1 과 3-2 에서 정의한 "시작 위치" 와 "마지막 위치" 는 문제 풀이를 하기 위한 탐색 경로 상의 위치이다.)

③ . 두 방식 모두 무한루프를 방지하기 위해 기저사례가 필요하다. 이 기저사례는 이전 항들로 표현되지 않는 상태의 값을 의미한다.

 

4 . 재귀 함수의 구간 별 의미

def recursive (index, output) {
	If ( 탈출 조건 with index ) {
		재귀함수에서 빠져 나와야 하는 기저사례
	}
	
	반복문 ( 부모가 여러 개 있을 경우 반복문 사용함. 부모가 한 개나 두 개인 경우 필요 없음 )
	{
		If ( /* 탐색하지 않아도 되는 부분들 */ ) continue
		recursive 함수 호출 (자식 탐방일 수 있고 상대 탐방일 수 있다)
	}
	부모로 돌아갈 때마다 해야될 일 (보통은 부모의 상태로 복원해야 하는 코드)
    해당 경우의 수 마지막 부분까지 온 경우이므로 마지막 자식 호출하고 난 다음에 해야될 일 (보통 계산)
}