구사과

Garey / Johnson의 1981년 논문 "Scheduling Unit-time tasks with Release time and Deadline" 를 읽고 내용을 정리해 보았다. Competitive Programming에서는 2017년 ICPC World Finals에서 한 명도 풀지 못했던 문제인 "Scenery"의 풀이로 유명한 논문이다. 이 글에서는 $O(n^2)$ 알고리즘까지만 정리했으며, $O(n\log n)$ 알고리즘은 하지 못했다. ㅠㅠ 이 문제의 $O(n^2)$ 알고리즘은 매우 아름답다. 혼자 생각하지 못하더라도 보고 배울 가치가 충분하니 일독을 권한다. 여담 : 예전에 breakun 님이 BOJ 슬랙에 질문했던 문제 중 하나이다. $N$개의 구간 $[S_i, T_i]$ 가 주어진..

이전에 Off-line dynamic connectivity에서 썼던 내용의 연장선으로, Dynamic MST 문제를 오프라인으로 푸는 알고리즘에 대한 글을 써 보았다.

5월 22일 KAIST RUN에서 봄 대회를 진행하였다. 대회는 백준 온라인 저지에서 진행하였으나 Open Contest의 경우 Codeforces Gym에서도 진행하였다.아래는 본 대회의 Scoreboard이다.ProblemsOpen Contest ScoreboardCodeforces Gym ArticleEditorialTests & Checker & Solutions