CAPS 위키 : DP

다이나믹 프로그래밍 DP에서 넘어옴. #DP #Dynamic Programming [ 수정 내역 ] [ 수정 ]

최근 수정:

목차

1. 개요

2. 용어

3. 조건

3.1. Overlapping Subproblem

3.2. Optimal Substructure

4. 구현

5. 푸는 방법

5.1. Top-down

5.2. Bottom-up

6.

1. 개요

Dynamic Programming. 줄여서 DP 라고 한다.

큰 문제를 작은 문제로 나누어 푸는 알고리즘 기법이다.

2. 용어

Dynamic Programming의 Dynamic은 아무 뜻이 없다...용어를 처음 사용한 사람[1]이 간지나서 썼다고 한다.

3. 조건

특정 문제를 DP로 풀려면 다음 두 가지 조건이 만족되어야 한다.

3.1. Overlapping Subproblem

겹치는 부분 문제가 있어야 한다.

3.2. Optimal Substructure

최적 부분 구조. 같은 문제는 구할 때마다 정답이 같다.

4. 구현

위의 두 가지 조건이 만족되었다면 구한 부분 문제의 정답을 어딘가에 메모해 놓는다. 이를 Memoization이라 한다. 코드의 구현에서는 배열에 저장하는 것이다.

5. 푸는 방법

5.1. Top-down

탑 다운. 한국어로는 하향식이라고 한다.

구하고자 하는 문제를 작은 부분 문제로 나누고 작은 문제의 답을 구한 후 정답을 바탕으로 원래 문제를 푸는 방식.

흔히 재귀함수로 구현한다.

5.2. Bottom-up

바텀 업. 한국어로는 상향식이라고 한다.

크기가 작은 부분 문제부터 차례로 풀어 나간다. 문제의 크기를 키우면서 답을 구한다. 보통은 마지막에 구한 답이 구하고자 하는 문제이다. [2]

흔히 반복문으로 구현한다.

6.

처음 DP를 배울 때엔 어려울 수도 있으므로 문제를 많이 풀어보자. BOJ에 DP문제들이 많이 있다.


[1] Richard Bellman

[2] 항상 마지막이 답은 아니다. 구한 후 최대값을 찾는다거나 하는 연산이 필요할 수도 있다.