✅ 오늘의 학습 키워드
- 그리디 알고리즘
- 우선순위 큐 (최소 힙)
- 문제 선택 최적화 전략
✍️ 공부한 내용 본인의 언어로 정리하기
오늘은 백준 1781번 문제인 컵라면 문제를 풀었다. 각 문제마다 데드라인과 해당 문제를 해결했을 때 받을 수 있는 컵라면 수가 주어진다. 하루에 한 문제씩만 풀 수 있을 때, 가장 많은 컵라면을 얻을 수 있는 문제 조합을 구하는 것이 목표다.
문제를 해결하기 위해 그리디 알고리즘 + 최소 힙 (min-heap) 조합을 사용했다. 핵심 전략은 다음과 같다:
- 문제들을 데드라인 오름차순으로 정렬한다.
- 문제를 순차적으로 선택하면서 현재까지 선택된 문제의 수가 해당 문제의 데드라인을 초과하는 경우, 가장 가치가 낮은 문제를 제거한다.
- 결국 남은 문제들은 데드라인 조건을 만족하면서 가장 높은 컵라면 수를 줄 수 있는 문제들만 남게 된다.
🧠 오늘의 회고
어떤 문제가 있었고, 나는 어떤 시도를 했는지
문제를 처음 봤을 때, 단순히 정렬해서 큰 컵라면 순서대로 풀면 될 거라 생각했는데, 데드라인 제약 때문에 단순 정렬로는 불가능하다는 걸 깨달았다.
어떻게 해결했는지
문제들을 데드라인 기준으로 정렬한 뒤, 하나씩 탐색하면서 우선순위 큐에 추가했다. 큐의 크기가 현재 문제의 데드라인보다 커지면 가장 컵라면 수가 적은 문제를 제거했다.
무엇을 새롭게 알았는지
- 그리디 + 우선순위 큐 조합이 매우 강력하다는 걸 체감했다.
- 데드라인처럼 선택의 수에 제약이 있는 문제는 큐로 유연하게 제어할 수 있다는 걸 배웠다.
*내일 학습할 것은 무엇인지 *
내일은 우선순위 큐를 활용한 다른 문제들을 더 풀어보고, 힙 자료구조의 활용 범위를 넓혀볼 계획이다.
📝 작성 코드
import sys
import heapq
input = sys.stdin.read
data = input().split()
N = int(data[0])
assignments = []
# 입력 데이터 파싱
index = 1
for _ in range(N):
deadline = int(data[index])
cup_ramen = int(data[index + 1])
assignments.append((deadline, cup_ramen))
index += 2
# 데드라인을 기준으로 정렬
assignments.sort()
min_heap = []
for deadline, cup_ramen in assignments:
heapq.heappush(min_heap, cup_ramen)
if len(min_heap) > deadline:
heapq.heappop(min_heap)
print(sum(min_heap))#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL
