DP(동적 계획법, Dynamic Programming ) - 유형정리

쳇 GPT 가 대표적인 DP 유형 10가지를 정리한 것을 공유드립니다.

---

✅ 1. 배낭 문제 (Knapsack DP)

✔ 특징: 배낭에 최대한 많은 가치를 넣는 문제.
✔ 예제 문제:

• 0/1 배낭: 백준 12865 - 평범한 배낭
• 무제한 배낭: 백준 2293 - 동전 1
• 다중 배낭: 백준 12920 - 평범한 배낭 2

점화식 예시 (0/1 배낭):

dp[w]=max⁡(dp[w],dp[w−weight]+value)dp[w] = \max(dp[w], dp[w - weight] + value)

---

✅ 2. LIS (Longest Increasing Subsequence, 최장 증가 부분 수열)

✔ 특징: 배열에서 가장 긴 증가하는 부분 수열을 찾는 문제.
✔ 예제 문제:

• 기본 LIS: 백준 11053 - 가장 긴 증가하는 부분 수열
• 최대 길이 LIS: 백준 14002 - 가장 긴 증가하는 부분 수열 4
• 2차원 LIS (가장 큰 직사각형): 백준 1915 - 가장 큰 정사각형

점화식 예시:

dp[i]=max⁡(dp[j]+1)(j < i, arr[j] < arr[i])dp[i] = \max(dp[j] + 1) \quad \text{(j < i, arr[j] < arr[i])}

---

✅ 3. LCS (Longest Common Subsequence, 최장 공통 부분 수열)

✔ 특징: 두 개의 문자열에서 가장 긴 공통 부분 수열을 찾는 문제.
✔ 예제 문제:

• 기본 LCS: 백준 9251 - LCS
• LCS 복원: 백준 9252 - LCS 2

점화식 예시:

dp[i][j]={dp[i−1][j−1]+1,(A[i] == B[j])max⁡(dp[i−1][j],dp[i][j−1]),(A[i] != B[j])dp[i][j] = \begin{cases} dp[i-1][j-1] + 1, & \text{(A[i] == B[j])} \\ \max(dp[i-1][j], dp[i][j-1]), & \text{(A[i] != B[j])} \end{cases}

---

✅ 4. DP + 비트마스킹

✔ 특징: 상태를 비트마스크로 표현하여 DP 테이블을 줄이는 문제.
✔ 예제 문제:

• 백준 2098 - 외판원 순회
• 백준 6987 - 월드컵

점화식 예시:

dp[cur][visited]=min⁡(dp[next][visited∣(1<<next)]+cost[cur][next])dp[cur][visited] = \min(dp[next][visited | (1 << next)] + cost[cur][next])

---

✅ 5. DP + 그래프 (Shortest Path DP)

✔ 특징: 최단 경로를 구하는 문제.
✔ 예제 문제:

• 백준 11404 - 플로이드
• 백준 12851 - 숨바꼭질 2

점화식 예시 (플로이드-워셜):

dp[i][j]=min⁡(dp[i][j],dp[i][k]+dp[k][j])dp[i][j] = \min(dp[i][j], dp[i][k] + dp[k][j])

---

✅ 6. DP + 문자열 (문자열 편집 거리, 문자열 개수 세기)

✔ 특징: 문자열을 변환하는 최소 비용을 구하거나, 특정 개수를 세는 문제.
✔ 예제 문제:

• 백준 9251 - LCS
• 백준 15483 - 최소 편집 거리

점화식 예시 (편집 거리):

dp[i][j]={dp[i−1][j−1],if A[i]==B[j]min⁡(dp[i−1][j],dp[i][j−1],dp[i−1][j−1])+1,otherwisedp[i][j] = \begin{cases} dp[i-1][j-1], & \text{if } A[i] == B[j] \\ \min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1, & \text{otherwise} \end{cases}

---

✅ 7. DP + 트리 (Tree DP)

✔ 특징: 트리에서 DP를 사용하여 서브트리 값을 누적하는 문제.
✔ 예제 문제:

• 백준 1949 - 우수 마을
• 백준 2533 - 사회망 서비스(SNS)

점화식 예시 (우수 마을 문제):

dp[node][0]=∑dp[child][1]dp[node][1]=value[node]+∑min⁡(dp[child][0],dp[child][1])dp[node][0] = \sum dp[child][1] dp[node][1] = value[node] + \sum \min(dp[child][0], dp[child][1])

---

✅ 8. DP + 확률 / 기대값 (Probability DP)

✔ 특징: 확률을 기반으로 DP를 갱신하는 문제.
✔ 예제 문제:

• 백준 15954 - 인형들 (표준편차)

점화식 예시:

dp[i]=∑j=1i(dp[j]×P(j,i))dp[i] = \sum_{j=1}^{i} (dp[j] \times P(j, i))

---

✅ 9. DP + 게임 (게임 이론 DP)

✔ 특징: 턴제 게임에서 승자를 판별하거나 최적의 전략을 구하는 문제.
✔ 예제 문제:

• 백준 9655 - 돌 게임
• 백준 11866 - 요세푸스 문제

점화식 예시 (돌 게임):

dp[n]=(dp[n-1]이 패배면 승리, 승리면 패배)dp[n] = \text{(dp[n-1]이 패배면 승리, 승리면 패배)}

---

✅ 10. DP + 구간 DP (Interval DP)

✔ 특징: 특정 범위를 나누어서 최적해를 찾는 문제.
✔ 예제 문제:

• 백준 11049 - 행렬 곱셈 순서
• 백준 15486 - 퇴사 2

점화식 예시 (행렬 곱셈 순서):

dp[i][j]=min⁡k(dp[i][k]+dp[k+1][j]+cost)dp[i][j] = \min_{k} (dp[i][k] + dp[k+1][j] + cost)

---

✅ 결론

✔ 배낭 문제, LIS/LCS, 그래프 최단 거리, 문자열 편집 거리 등 다양한 DP 유형이 존재!
✔ 문제 유형에 따라 1차원 DP, 2차원 DP, 비트마스킹 DP 등을 적용해야 함!