✅ 1단계. DP 조건 확인
- 최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있는가?
- 중복 하위 문제: 같은 하위 문제가 반복 발생하는가?
➡️ 이 두 가지가 있으면 DP로
구분 🚨DFS ✅ DP (TopDown) 🗝️ 백트래킹 목적 끝까지 탐색 중복 방지 + 최적값 계산 조건 만족하는 해를 빠르게 찾기 중간 값 저장 ❌ 없음 ✅ 있음 (memo 배열 등) ❌ 없음 중복 계산 방지 ❌ 불가능 ✅ 가능 ❌ 불가능 (대신 조건으로 방지) 예시 미로 탐색 피보나치, 판다 N-Queen, 순열, 조합 가지치기 ❌ ✅ 경우에 따라 ✅ 핵심 로직 최적값 문제 해결 ❌ 비효율 ✅ 적합 ❌ 적합 아님
✅ 2단계. 상태(state) 정의 👉🏻 추적 개수에 따라 차원 설정
dp[i], dp[i][j], dp[i][j][dir] 등으로
어떤 정보를 기억하면 문제를 풀 수 있는지를 먼저 정의해야 함
✅ 3단계. 탐색 방향 및 구조 판단
🔹Bottom-Up vs 🔸Top-Down 결정
🎯 Bottom-Up이 적합한 경우
🔹 계단 점프, 진우의 달 여행, 최소 동전 개수 🔹
| 판단 기준 | 설명 |
|---|---|
| 🔹 탐색 방향이 정해져 있음 | 예: 위에서 아래, 왼쪽에서 오른쪽, 앞에서 뒤 등 |
| 🔹 시작점과 도착점이 명확함 | 예: 시작은 항상 0이고 끝은 N-1 등 |
| 🔹 모든 상태를 반드시 계산해야 함 | 경로가 고정돼 있고, 전체 테이블을 다 채워야 함 |
| 🔹 DFS가 오히려 느리거나 복잡함 | ex: 경로 수가 많아 중복 방문이 잦은 경우 |
🎯 Top-Down (재귀 + 메모이제이션)이 적합한 경우
🔸 판다 문제, 가장 긴 증가 부분 수열(탑다운 방식), 특정 트리 탐색 🔸
| 판단 기준 | 설명 |
|---|---|
| 🔸 탐색 방향이 자유롭고 분기 구조임 | 상하좌우 자유 탐색, 나무 구조처럼 갈라짐 |
| 🔸 시작점이 여러 개거나 미정임 | 모든 칸에서 출발 가능, 최댓값 찾기 등 |
| 🔸 일부 상태만 탐색하면 됨 | 전체 테이블을 다 채울 필요 없음 |
| 🔸 DFS로 가지치기 하면서 효율적으로 접근 가능 | 필요할 때만 계산함 |
✅ 결정 흐름도
Q??
│
├─ 탐색 방향이 일정한가? (ex: 위→아래, 왼→오)
│ └─ YES → Bottom-Up DP
│
├─ 시작점/도착점이 명확한가?
│ └─ YES → Bottom-Up DP
│
├─ 탐색 방향이 자유롭고 구조가 분기형인가?
│ └─ YES → Top-Down (DFS + 메모이제이션)
│
└─ 모든 상태를 계산해야 하나, DFS가 느릴까?
└─ YES → Bottom-Up 선호
with me