[D+14] 오늘의 발자국

1. 오늘의 몰입: 그리디의 다변화

주요 목표

• 코딩 테스트 집중 훈련: 백준 골드 그리디 10문제 풀이
  • 유형
    • + 스위핑 & PQ: 호텔 방 배정(9203), 강의실 배정 2(1379)
    • + 파라메트릭 서치: 제자리 멀리뛰기(6209)
    • + 반례 교체(Replacement): 2000원(19582)
    • + 비트마스킹/기하: 비밀번호(2464), 이사(17371)

달성률: 100%

2. 오늘의 난관 (성장)

• 안정적인 멘탈: 문제가 안 풀릴 때 스트레스를 받지 않고자 더욱 노력해야겠다.

3. 배움과 기록: 고급 그리디 패턴

오늘 푼 문제들에서 발견한 중요한 기출 패턴 두 가지를 정리한다.

💡 1. Replacement Strategy

• 문제: 2000원(19582), 좀비(19644)
• 패턴: 일단 현재 선택을 수행한다. 그러다 조건(예산, 체력 등)을 초과하게 되면, “과거의 선택 중 가장 비효율적인 것”을 버리고 현재의 효율적인 것으로 교체한다.
• 도구: PriorityQueue (Max Heap)을 사용하여 과거의 선택 중 가장 비용이 큰 것을 $O(\log N)$으로 찾아낸다.

💡 2. Sweeping

• 문제: 강의실 2(1379), 호텔(9203)
• 패턴: 시작 시간과 종료 시간을 기준으로 정렬한 뒤, 시간의 흐름에 따라 이벤트를 처리한다.
• 핵심: “현재 사용 중인 회의실 중 가장 빨리 끝나는 시간”을 알기 위해 PriorityQueue (Min Heap)에 종료 시간을 넣고 비교한다.

4. 내일의 다짐

• 그리디 지속: 내일까지 그리디 10문제를 채우면, 5일간 50문제의 그리디 유형을 풀이하게 된다.