DP

DP(Dynamic Programming)는 암기 과목이 아니라 '문제를 쪼개서 생각하는 사고법'에 가깝습니다. 특정 유형을 외우기보다, 어떤 문제든 DP로 풀 수 있게 만드는 '생각의 틀'을 잡는 것이 중요합니다.

---

DP 정복을 위한 4단계 공부법

DP를 효과적으로 공부하기 위한 체계적인 접근법입니다.

1단계: 핵심 개념 이해하기 💡

DP의 두 가지 대표적인 방식, 메모이제이션(Memoization)과 타뷸레이션(Tabulation)의 차이를 이해하는 것부터 시작해라.

• 메모이제이션 (Top-down): 큰 문제를 재귀 호출로 풀어나가되, 한 번 계산한 결과는 기록해두고 재사용하는 방식입니다. 로직이 직관적이라 처음 접근하기 좋습니다.
• 타뷸레이션 (Bottom-up): 가장 작은 문제부터 차례대로 정답을 구해 테이블을 채워나가는 방식입니다. 보통 반복문으로 구현하며 성능이 더 좋은 경우가 많습니다.

처음에는 어떤 방식이든 하나만 정해서 익숙해지는 것을 추천합니다. 대부분의 코딩 테스트에서는 Bottom-up 방식이 주로 사용됩니다.

---

2단계: '생각의 틀' 훈련하기 💪

새로운 DP 문제를 만났을 때, 항상 아래 3가지 질문을 스스로에게 던지는 연습을 하세요.

1. DP 상태 정의 (dp[i]는 무엇인가?): dp 배열의 각 칸이 어떤 의미를 갖는지 명확하게 정의해야 합니다.

   • (예: dp[i] = i원을 만드는 동전의 최소 개수)
   • (예: dp[i] = i번째 집까지 칠하는 최소 비용)

2. 점화식 찾기 (dp[i]와 이전 값들의 관계는?): i번째 문제의 정답(dp[i])을 그보다 작은 문제들의 정답(dp[i-1], dp[i-2] 등)을 이용해 어떻게 구할 수 있을지 고민합니다. 여기가 DP의 핵심입니다.

   • (예: dp[i]는 dp[i-1]과 dp[i-2]를 더한 값이다.)
   • (예: dp[i]는 dp[i-1], dp[i-2], dp[i-5] 중 최솟값에 1을 더한 값이다.)

3. 초기값 설정 (Base Case는 무엇인가?): 점화식이 시작될 수 있는 가장 작은 문제의 정답(dp[0], dp[1] 등)을 직접 계산해서 dp 배열에 넣어줍니다. 이 기반이 없으면 점화식이 무너집니다.

---

3단계: 유형별 문제 풀기 ✅

무작위로 풀기보다, 클래식한 유형별로 묶어서 풀며 패턴을 익히는 것이 효과적입니다.

• 기본 다지기: 1차원 DP 배열을 사용하는 가장 기초적인 문제들
• 응용하기: 2차원 DP 배열, 배낭(Knapsack), LIS(가장 긴 증가하는 부분 수열) 등 유명한 유형들

---

4단계: 다른 사람의 코드 보기 👀

문제를 푼 후에 다른 사람들은 어떻게 풀었는지 꼭 확인해라. 같은 문제라도 점화식을 다르게 세우거나, DP 상태를 더 효율적으로 정의하는 방법을 배울 수 있습니다.

---

레벨별 추천 문제 (백준)

아래 문제들을 순서대로 풀어보시면 DP에 대한 감을 잡는 데 큰 도움이 될 겁니다.

LV 1: DP와 친해지기 (핵심 원리)

• 1463번: 1로 만들기
  • DP의 가장 기본이 되는 문제입니다. '생각의 틀 3단계'를 적용하는 연습을 하기에 완벽합니다.
• 11726번: 2×n 타일링
  • 매우 유명한 피보나치 수열의 변형 문제입니다. 간단한 점화식을 세우는 연습을 할 수 있습니다.
• 9095번: 1, 2, 3 더하기
  • dp[i]를 정의하고, i-1, i-2, i-3과의 관계를 찾는 연습을 하기에 좋습니다.
• 2579번: 계단 오르기
  • 이미 푸셨지만, 지금의 지식으로 다시 한번 점화식을 유도해보세요. 왜 그런 로직이 나왔는지 완벽히 이해하는 것이 중요합니다.

LV 2: 조금 더 생각하기 (1차원 DP 응용)

• 11053번: 가장 긴 증가하는 부분 수열 (LIS)
  • DP의 대표 유형 중 하나인 LIS의 가장 기초적인 문제입니다.
• 1912번: 연속합
  • 이전 값들을 누적하는 방식에 대한 새로운 아이디어를 얻을 수 있습니다.
• 1149번: RGB거리
  • dp 배열을 2차원으로 확장(dp[i][색깔])하는 첫걸음입니다.

LV 3: 유명 유형 정복하기

• 12865번: 평범한 배낭
  • 모든 코딩 테스트의 단골손님, 배낭(Knapsack) 문제의 가장 표준적인 형태입니다. 이 문제는 풀이법을 거의 외워둘 가치가 있습니다.
• 9251번: LCS (최장 공통 부분 수열)
  • 두 문자열을 다루는 대표적인 2차원 DP 문제입니다.