🚨오늘의 학습🚨
⭐️ DP란? 왜 사용하는 걸까?⭐️
🎯 "어떤 선택을 해야 가장 최적의 결과를 얻을까?" -> 🔸 재귀 / 반복
🎯 "이전에 구해둔 결과를 재사용할 수 있을까?" -> 🔸 메모제이션
🗝️ Top-Down : “현재칸에서 다음칸으로 이동한다”
🗝️ Bottom-Up : “현재칸에 도달하기 위해 어떤 경로로 왔을까?”를 생각해야 해.
✅ Step 1. 문제를 ‘선택 + 최적화’ 문제로 바꿔 읽기
✅ Step 2. 패턴 찾기 ➡️ 점화식을 고민 (작은 문제 → 큰 문제)
✅ Step 3. 함수의 반환값은 무엇인가? → 이게 곧 dp[i]의 정의(규칙 패턴 적용)
✅ Step 4. 방식 결정: Top-down(재귀+메모이제이션) / Bottom-up(반복)
🔁 Bottom-up (반복문 기반, 배열 채워나감)
💡 모든 경우를 아래 ➡️ 위로 쌓는다
- 장점: 속도 빠름, 호출 스택 없음
- 단점: 메모리 사용 클 수 있음
🔄 Top-down (재귀 + 메모제이션)
💡최종 결과부터 의존관계를 따라가며 구성
- 장점: 코딩 직관적, 필요한 곳만 탐색
- 단점: 재귀 깊이 많으면 StackOverflow 가능
✅ Step 5. 초기값을 정의하자
- 재귀에서 if (i == 0) 같은 확실한 불변의 조건
- 반복문에서는 dp[0], dp[1]
🔸 초기값은 점화식이 뻗어나갈 기반
with me