기본 개념
- Overlapping Subproblems (겹치는 부분 문제)
- 동일한 작은 문제가 반복적으로 계산되어야 함
- 매번 계산하지 않고 처음 한 번 계산한 값을 배열에 저장해두었다가 다음에 수행 시 값을 갖고 온다. 예시: 피보나치 수열에서 fib(5) = fib(4) + fib(3) → fib(3)은 fib(4)와 fib(5) 계산에 모두 사용
- Optimal Substructure (최적 부분 구조)
- 상위 문제의 최적해가 하위 문제의 최적해 조합으로 구성 가능
예시: 최단 경로 문제에서 A→C 부단 경로 = A→B 최단 경로 + B→C 최단 경로
- 상위 문제의 최적해가 하위 문제의 최적해 조합으로 구성 가능
구현 순서
- 구현하고 싶은 문제를 작은 문제로 나누다. (점화식)
- fib(n) = fib(n-1) + fib(n-2)
- 초기 값을 설정한다.(Base Case)
- fib(1) = 1, fib(2) = 2
- 저장 메커니즘을 설정한다.
- 탑다운: 재귀 + 메모이제이션
- 바텀업: 반복문 + DP 테이블 이용
- 계산 완료 및 결과 추출
예제
증가하는 부분 수열
- 배열 내에서 증가하는 부분 수열 중에서 최대 합을 구하는 문제입니다.
접근 개념
아래와 같은 기본 배열이 있다고 가정을 한다면
int[] store = {1, 100, 2, 50, 60, 3, 5, 6}
자신의 인덱스의 이전 값들을 비교하면서 자신보다 작은 경우 값을 더해주거나 연속 길이를 더해준다.
STEP 1
| index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| store | 3 | 7 | 5 | 2 | 6 | 1 | 4 | 8 |
| dp 초기값 | 3 | 7 | 5 | 2 | 6 | 1 | 4 | 8 |
| dp 최종값 | 3 | 10 |
STEP 2
인덱스 3에서 앞의 인덱스 1과 2의 값을 확인 하고 5보다 작은 3과의 합을 DP에 저장해 둔다.
| index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| store | 3 | 7 | 5 | 2 | 6 | 1 | 4 | 8 |
| dp 초기값 | 3 | 7 | 5 | 2 | 6 | 1 | 4 | 8 |
| dp 최종값 | 3 | 10 | 8 |
STEP 3
인덱스 4에서 앞의 인덱스 1, 2, 3의 값을 확인해보면 더 작은 값이 없으니 그대로 2를 기록한다.
| index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| store | 3 | 7 | 5 | 2 | 6 | 1 | 4 | 8 |
| dp 초기값 | 3 | 7 | 5 | 2 | 6 | 1 | 4 | 8 |
| dp 최종값 | 3 | 10 | 8 | 2 | ||||
| … |
Last STEP
| index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| store | 3 | 7 | 5 | 2 | 6 | 1 | 4 | 8 |
| dp 초기값 | 3 | 7 | 5 | 2 | 6 | 1 | 4 | 8 |
| dp 최종값 | 3 | 10 | 8 | 2 | 14 | 1 | 7 | 22 |
연속되는 수열 중에 가장 큰 값
// 저장 배열
int[] dp = new int[n]; // 합들을 저장
int[] store = new int[n]; // 기존의 입력값을 저장하는 배열
dp[0] = store[0];
for (int i = 1; i < store.length; i++) {
int max = store[i];
// 이전 값을 확인
for (int j = 0; j < i; j++) {
// 이전 배열에서 값이 작은 경우 최대값을 구한다.
if (store[i] > store[j]) {
max = Math.max(dp[j] + store[i], max);
}
}
dp[i] = max;
}최소한의 움직임으로 정렬하기
문제 링크
최소한의 움직임으로 배열의 내부의 값을 정렬하기 위해서 현재 배열에서 가장 긴 연속 배열을 찾는다.
int[] dp = new int[n]; // 합들을 저장
int[] store = new int[n]; // 기존의 입력값을 저장하는 배열
dp[0] = 1; // 연속 길이 1
for (int i = 1; i < store.length; i++) {
int max = 1;
// 이전 값을 확인
for (int j = 0; j < i; j++) {
// 더 크면 뒤의 길이가 긴 부분을 저장한다.
if (store[i] > store[j]) {
max = Math.max(dp[j] + 1, max);
}
}
dp[i] = max;
}이중 제약 조건을 갖는 최적화 문제
접근 방법
상태 정의
dp[i][j]: 인덱스i개 까지 진행했을 때, B가 남긴 흔적의 합이j인 경우의 최소 A 흔적 그룹 합
점화식 작성
- 인덱스 i 까지 진행했을 때 A가 흔적을 남긴 경우
dp[i][j] = min(dp[i][j], dp[i-1][j] + a)- 인덱스 i 까지 진행했을 때 B가 흔적을 남긴 경우
if (j + b < m) {
dp[i][j + b] = min(dp[i][j + b], dp[i-1][j])
}처음 시작 부분 초기화
- 처음 A를 고른 경우
- A를 골랐으므로 B의 흔적값은 안오르고 배열 값이 올라야 한다.
dp[0][0] = info[0][0]; // a가 선택된 경우- 처음 B를 고른 경우
- 만약 현재 B의 데이터가 임계값을 넘은 경우 고르지 않는다.
if (info[0][1] < m) {
dp[0][info[0][1]] = 0;
}주요 로직
초기화 된 이후 값 부터 A의 흔적값의 최솟값을 채워나간다.
for (int i = 1; i < info.length; i++) {
int a = info[i][0];
int b = info[i][1];
// dp에 A를 골랐을 때와 B를 골랐을 때의 최솟값으로 저장해준다.
for (int j = 0; j < m; j++) {
dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + a);
if (j + b < m) {
dp[i][j + b] = Math.min(dp[i][j + b], dp[i - 1][j]);
}
}
}여기서 입력값은 정해져 있어서 모든 j의 경우의 수를 찾아보는 것이 이해가 되지 않았었는데 아래와 같이 이유이다.
- 요소 할당의 조합 다양성:
각 요소를 A/B 중 어디에 넣을지 선택할 때마다 B 합j가 변화합니다.
→ 모든 가능한j를 추적하지 않으면 최적의 조합을 놓칠 수 있습니다. - 부분문제 중복:
다른 경로로 동일한j에 도달할 수 있으므로, 최소 A 합을 비교·갱신해야 합니다.