Skip to content

dp.md

Latest commit

 

History

History
116 lines (71 loc) · 2.55 KB

dp.md

File metadata and controls

116 lines (71 loc) · 2.55 KB
Raw

DP

  • "어떤 문제의 답을 구하기 위해 동일한 계산을 반복해야 할 때, 한 번 계산한 결과를 메모리에 저장해 재활용하는 기법"

DP가 가능한 2가지 조건

1. 중복되는 부분 문제 (Overlapping Subproblems)

  • 동일한 작은 문제들이 반복해서 나타남

2. 최적 부분 구조 (Optimal Substructure)

  • 작은 문제의 최적해로 큰 문제의 최적해를 구성할 수 있음

접근 방법

1. Top-Down (메모이제이션)

  • 재귀 + 메모리에 저장
  • 큰 문제에서 시작해 작은 문제로

2. Bottom-Up (타뷸레이션)

  • 반복문 사용
  • 작은 문제부터 차근차근 해결

문제 해결 단계

1. 상태 정의하기

  • dp[i]가 무엇을 의미하는지 명확히 정의
  • 예: dp[i] = i번째까지 고려했을 때의 최적해

2. 점화식 세우기

  • 작은 문제와 큰 문제의 관계식
  • 예: dp[i] = dp[i-1] + dp[i-2]

3. 초기값 설정

  • 가장 작은 문제의 답
  • 예: dp[0] = 0, dp[1] = 1

4. 계산 순서 정하기

  • 작은 문제부터 차례대로
  • 의존 관계 고려

5. 답 추출하기

  • 보통 dp[n] 또는 dp 배열의 최댓값

DP 문제 판별하기

✅ DP 신호

  • "최대", "최소", "가장 긴", "가장 짧은"
  • "~하는 방법의 수"
  • "모든 경우를 고려해야 함"
  • 그리디로 반례가 있음

📝 상태 정의 예시

  • dp[i] = i번째 원소까지 고려했을 때의 최적해
  • dp[i][j] = i번째부터 j번째까지의 최적해
  • dp[i][w] = i번째까지, 용량 w일 때의 최적해

실전 팁

1. 작은 예시로 손으로 풀어보기

  • 패턴 발견이 중요

2. 점화식이 핵심

  • 점화식만 세우면 80% 해결

3. 공간 최적화는 나중에

  • 먼저 정확히 풀고, 필요하면 최적화

4. 디버깅할 때

  • DP 테이블 출력해서 확인

그리디와의 차이?

선택의 되돌림

그리디 (Greedy)

  • 한 번 선택하면 끝 - 되돌릴 수 없음
  • 현재 상황에서 최선만 선택
  • "지금 당장" 좋은 것을 선택

DP (Dynamic Programming)

  • 모든 경우를 다 계산해서 비교
  • 이전의 모든 가능성을 고려
  • "전체적으로" 최적인 것을 선택

실전에서 구분하는 법

문제를 보고...

1. "매 순간 명확한 최선이 있나?"
   → YES: 그리디 시도
   → NO: DP 고려

2. "한 번 선택하면 끝인가?"
   → YES: 그리디 가능
   → NO: DP 필요

3. "부분 최적해 = 전체 최적해?"
   → YES: 그리디 가능
   → NO: DP 필요