DP vs. Stack vs. Heapq

🔹 DP / Stack의 본질

과거에서부터 일직선으로 작동한다.

무슨 의미냐 하면은

DP

• 상태가 dp[i] → dp[i+1]로 단방향
• 한 번 계산된 과거 상태는 되돌리지 않음
• 과거 선택이 “최선”이라는 전제 하에 누적

👉 그래서
✔ “지금 선택이 나중에 틀릴 수 있는 문제”에는 부적합

---

Stack

• 가장 최근 선택만 취소 가능 (LIFO)
• “조건 위반 시, 방금 넣은 것만 제거” 가능
• 임의의 과거 선택 제거 불가능

👉 백준) 컵라면 문제에서:

• 제거해야 할 건 “가장 컵라면 적은 문제”
• 이게 꼭 마지막에 넣은 것이 아니다 ❌

---

🔹 Heap(우선순위 큐)의 본질

우선순위 기준으로 과거 선택을 언제든지 되돌릴 수 있다

 

이게 힙의 핵심 능력 🔥

• 힙은 시간 순서가 아니라 가치 순서로 관리
• 따라서 과거에 “최선처럼 보였던 선택”도 더 좋은 선택이 오면 즉시 폐기 가능

👉 그래서 힙은 이런 문제에 강함:

• “일단 다 넣어본다”
• “조건 위반 시, 제일 나쁜 것 하나 제거”

---

📌 컵라면 문제로 다시 연결해보면

상황

• 데드라인 2까지는 문제 2개만 가능
• 이미 2개를 골랐는데
• 컵라면 100짜리 문제가 새로 등장함

해야 할 일

• 과거 선택 중 컵라면 최소를 제거
• 이게 언제 들어온 문제인지는 중요 ❌

👉 힙만 가능

---

즉,

DP나 스택은 과거 선택이 한 방향으로만 누적되며, 한 번 선택한 것이 나중에 뒤집히지 않는다.
반면 heapq는 우선순위를 기준으로 관리되기 때문에 과거에 최선이라고 선택한 것도 나중에 더 좋은 선택이 나오면 즉시 되돌릴 수 있다.

---

🔥 코테용 암기 포인트!

“과거 선택을 나중에 우선순위로 취소해야 하면 힙을 쓰자.”