[C++] 다이나믹 프로그래밍 - AI 개념 정리

DP(Dynamic Programming) 핵심 정리

DP는 이전에 계산한 결과를 저장해두고, 다음 계산에서 재사용하는 방식이다.

핵심은 코드를 외우는 게 아니라 먼저

dp[i]가 무슨 뜻인지 정의하는 것

이다.

---

1. DP 문제 풀이 순서

DP 문제를 보면 이 순서로 생각한다.

① dp[i]가 무엇을 의미하는가?

② 현재 상태에서 어떤 선택이 가능한가?

③ 그 선택을 이전/다음 dp와 어떻게 연결하는가?

④ 최대값인가? → max
   최소값인가? → min
   경우의 수인가? → +

⑤ 어떤 값이 먼저 계산되어 있어야 하는가?
   → 반복 방향 결정

⑥ 초기값 설정

예를 들어:

dp[i] = i일까지 얻을 수 있는 최대 수익

이라고 정의했다면,

오늘 일을 한다
오늘 일을 안 한다

두 경우를 비교해서:

dp[i] = max(한다, 안 한다);

라는 점화식을 만든다.

---

2. 점화식

점화식은

현재 dp 값을 이미 계산한 다른 dp 값으로 표현하는 식

이다.

예를 들어 계단을 1칸 또는 2칸씩 올라간다면:

dp[i] = dp[i-1] + dp[i-2];

의미는:

i번째까지 오는 방법
=
i-1에서 오는 방법
+
i-2에서 오는 방법

---

3. 최대값 DP

문제에서 이런 말이 나오면 max()를 생각한다.

최대 수익
최대 점수
최대 개수
최장 길이

대표 형태:

dp[i] = max(
    현재 것을 선택하지 않는 경우,
    현재 것을 선택하는 경우
);

예:

dp[i] = max(
    dp[i-1],
    dp[i-2] + arr[i]
);

의미:

현재 선택 X → dp[i-1]

현재 선택 O → dp[i-2] + arr[i]

둘 중 큰 값

---

4. 최소값 DP

이런 문제가 나오면 min()을 생각한다.

최소 비용
최소 횟수
최소 시간
최소 이동

대표 형태:

dp[i] = min(
    방법1,
    방법2
);

예:

dp[i] = min(
    dp[i-1],
    dp[i-2]
) + cost[i];

즉:

여러 방법으로 i에 도착할 수 있다
→ 그중 가장 싼 방법 선택

---

5. 경우의 수 DP

최대/최소가 아니라 몇 가지 방법이 있는지 묻는 경우는 더한다.

dp[i] = dp[i-1] + dp[i-2];

예:

1칸 전에서 오는 경우
+
2칸 전에서 오는 경우

---

6. DP를 앞에서부터 할지 뒤에서부터 할지

이 부분이 중요하다.

앞에서부터

점화식이 이전 값을 필요로 한다면:

dp[i] = max(dp[i-1], dp[i-2] + value[i]);

dp[i-1], dp[i-2]가 먼저 있어야 하니까:

for(int i = 2; i < N; i++){
    ...
}

앞에서 뒤로 간다.

흐름:

dp[0]
  ↓
dp[1]
  ↓
dp[2]
  ↓
dp[3]

---

뒤에서부터

반대로 점화식이 미래 값을 필요로 한다면:

dp[i] = max(
    dp[i+1],
    value[i] + dp[i + time[i]]
);

dp[i+1], dp[i+time[i]]가 먼저 계산돼 있어야 한다.

따라서:

for(int i = N-1; i >= 0; i--){
    ...
}

뒤에서 앞으로 간다.

흐름:

dp[N]
   ↓
dp[N-1]
   ↓
dp[N-2]
   ↓
...

판단 기준

dp[i]가 dp[i-1], dp[i-2]를 사용
→ 앞에서부터

dp[i]가 dp[i+1], dp[i+k]를 사용
→ 뒤에서부터

DP 방향을 외우는 게 아니라, 필요한 값이 먼저 계산되도록 하면 된다.

---

7. 상담 문제로 보는 뒤에서부터 DP

예를 들어:

dp[i] = i일부터 마지막 날까지 벌 수 있는 최대 수익

현재 i일에서:

① 상담 안 함
→ dp[i+1]

② 상담 함
→ P[i] + dp[i + T[i]]

따라서:

dp[i] = max(
    dp[i+1],
    P[i] + dp[i + T[i]]
);

전체:

vector<int> dp(N + 1, 0);

for(int i = N-1; i >= 0; i--){

    if(i + T[i] <= N){

        dp[i] = max(
            dp[i+1],
            P[i] + dp[i + T[i]]
        );

    }
    else{
        dp[i] = dp[i+1];
    }
}

---

8. 초기값

DP에서는 점화식만큼 초기값도 중요하다.

예를 들어:

dp[i] = dp[i-1] + dp[i-2];

라면 dp[0], dp[1]은 점화식으로 만들 수 없다.

따라서 직접 설정한다.

dp[0] = 1;
dp[1] = 1;

for(int i = 2; i < N; i++){
    dp[i] = dp[i-1] + dp[i-2];
}

정리하면:

점화식을 적용할 수 없는 처음 값
→ 직접 초기화

---

9. Bottom-Up vs Top-Down

Bottom-Up

반복문으로 작은 값부터 계산한다.

for(int i = 2; i < N; i++){
    dp[i] = max(
        dp[i-1],
        dp[i-2] + arr[i]
    );
}

보통 코딩테스트에서는 이 방식이 가장 직관적이다.

---

Top-Down + Memoization

재귀 DFS를 사용한다.

int DFS(int i){

    if(dp[i] != -1)
        return dp[i];

    return dp[i] = max(
        DFS(i-1),
        DFS(i-2) + arr[i]
    );
}

흐름은:

DFS(i)
   ↓
필요한 이전 상태 호출
   ↓
계산
   ↓
dp에 저장

같은 상태를 또 만나면:

if(dp[i] != -1)
    return dp[i];

해서 다시 계산하지 않는다.

본질적으로 Bottom-Up과 같은 DP다.

---

10. 2차원 DP

DP 배열이 반드시 1차원일 필요는 없다.

예를 들어 격자에서 위/왼쪽에서만 이동 가능하고 최대 점수를 구한다면:

dp[y][x] =
    max(
        dp[y-1][x],
        dp[y][x-1]
    )
    + arr[y][x];

최소 비용이면:

dp[y][x] =
    min(
        dp[y-1][x],
        dp[y][x-1]
    )
    + arr[y][x];

즉:

현재 위치까지 오는 여러 방법
→ 이전 상태 중 최적값 선택
→ 현재 값 추가

---

DP 문제를 봤을 때 체크리스트

• dp[i]를 한 문장으로 정의할 수 있는가?
• 현재 상태에서 선택지가 무엇인가?
• 최대면 max, 최소면 min, 경우의 수면 +
• dp[i]가 어느 상태를 참고하는가?
• 이전 값을 참고하면 앞에서부터
• 다음 값을 참고하면 뒤에서부터
• 반복 계산되는 상태가 있다면 DP 가능성 확인
• 처음 몇 개의 초기값은 직접 설정

---

연계해서 풀기 좋은 문제

~ 근데 BOJ 지금 막혔는데? ..~

지금은 DP 유형을 다양하게 많이 풀기보다 각 형태를 하나씩 익히는 게 좋아.

유형추천 문제핵심

기본 경우의 수	BOJ 1463 1로 만들기	최소 연산 횟수
기본 경우의 수	BOJ 9095 1, 2, 3 더하기	이전 경우의 수 합
기본 max	BOJ 2579 계단 오르기	선택/미선택 + 최대값
기본 max	BOJ 2156 포도주 시식	연속 선택 조건
뒤에서 DP	BOJ 14501 퇴사	상담 한다/안 한다
냅색 입문	BOJ 12865 평범한 배낭	선택/미선택 DP
2차원 DP	BOJ 1149 RGB거리	이전 상태 중 최소
격자 DP	BOJ 1932 정수 삼각형	위에서 내려오며 최대
Top-Down 연습	BOJ 1932 또는 1463을 재귀+memo로 다시 풀기	메모이제이션 감 잡기

지금 준비 단계라면 우선순위는:

14501 퇴사
→ 1463 1로 만들기
→ 2579 계단 오르기
→ 1932 정수 삼각형
→ 1149 RGB거리
→ 12865 배낭