동적 계획법 (DP) 정리
동적 계획법(Dynamic Programming) 정리
큰 문제를 작은 문제로 나눠서 푸는 알고리즘인데, 코딩테스트에서 자주 출제되는 알고리즘 기법입니다.
DP 속성
- Overlapping Subproblem (부분 문제가 겹친다.)
- Optimal Substructure (최적 부분 구조)
Overlapping Subproblem
대표적인 예로 피보나치 수를 들 수 있다.
Fn = Fn-1 + Fn-2
여기서 Fn을 큰 문제로 생각하고, 우측 항에 있는 Fn-1, Fn-2를 작은 문제로 나눈다고 생각하면 된다.
Optimal Substructure
문제의 정답을 작은 문제의 정답을 합하는 것으로 구할 수 있다.
위의 예에서 작은 문제로 쪼갠 우측항의 Fn-1 + Fn-2로 큰 문제인 Fn의 값을 구할 수 있다.
그렇다면 어떻게 해야하는 가?
DP는 Optimal Substructure를 만족하기 때문에 작은 문제로 큰 문제의 정답을 구할 수 있다.
이때, 작은 문제의 정답을 메모해둔다. (코드에서는 배열로써 구현함)
int memo[100];
public int fibonacci(int n) {
if (n <= 1)
return n;
else if (n == 2)
return 1;
else {
if (memo[n] > 0)
return memo[n];
memo[n] = fibonacci(n-1) + fibonacci(n-2);
return memo[n];
}
}
그런데 DP를 풀 때 어떤 방식으로 접근해야하는 가?
- Top-Down
- Bottom-Up
Top-Down
- 큰 문제를 작은 문제로 나눈다.
F(n-1), F(n-2)로 나눈다. - 작은 문제를 푼다.
F(n-1) + F(n-2)
재귀호출을 하는 방식으로 푼다.
Bottom-Up
- 문제를 크기가 작은 문제부터 차례대로 쓴다.
- 문제의 크기를 조금씩 크게 만들면서 문제를 푼다.
- 작은 문제를 풀면서 큰 문제의 답을 구한다.
int d[100];
public int fibonacci(int n) {
d[0] = 0;
d[1] = 1;
for (int i = 2; i <= n; i++) {
d[i] = d[i - 1] + d[i - 2];
}
return d[n];
}
- 1463번 1로 만들기
- 11726번 2xn 타일링
- 11727번 2xn 타일링2
- 9095번 1,2,3 더하기
- 15988번 1,2,3 더하기3
- 11052번 카드 구매하기
- 16194번 카드 구매하기2
- 10844번 쉬운 계단 수
- 11057번 오르막 수
- 2193번 이친수
- 2156번 포도주 시식
마지막 오는 숫자를 케이스로 나눠서 푸는 문제
- 11053번 가장 긴 증가하는 부분 수열
- 14002번 가장 긴 증가하는 부분 수열4
- 11722번 가장 긴 감소하는 부분 수열
- 11054번 가장 긴 바이토닉 부분 수열
- 1912번 연속합
- 1699번 제곱수의 합
- 2293번 동전 1
- 2294번 동전 2
동전 2는 DP와 BFS로 풀 수 있는 문제이다. 두 가지 방법으로 풀어보는 것을 추천한다.
'기타 정보 > 코딩테스트' 카테고리의 다른 글
깊이 우선 탐색 (DFS) 정리 (1) | 2023.09.14 |
---|---|
너비 우선 탐색 (BFS) 정리 (0) | 2023.09.14 |
java int 배열을 List로 변환 (0) | 2023.09.14 |
java 배열을 List로, List를 배열로 변환 (0) | 2023.09.14 |
java Character 메소드 (0) | 2023.09.14 |
java String 메소드 (0) | 2023.09.14 |
String을 int로, int를 String으로 변환 (0) | 2023.09.14 |
java 배열 메소드 (0) | 2023.09.14 |