구사과

IOI 2021 Day 2 대회가 종료되었다. 올해 대회의 개최지는 싱가포르지만, COVID-19로 인하여 현장 대회는 취소되었다. 대회는 모두 온라인으로 진행되며, 한국 학생들은 서울에서 모여서 감독 하에 대회를 진행하고 있다. 한국 학생들의 최종 성적은 다음과 같다. 메달 결과는 1금 2은 1동이다. 반딧불, 100 / 67 / 70 / 100 / 62 / 75, 474점, 7등, 금메달 송준혁, 38 / 37 / 100 / 100 / 50 / 46, 371점, 31등, 은메달 최서현, 100 / 9 / 5 / 100 / 89 / 33, 336점, 47등, 은메달 장태환, 11 / 37 / 70 / 100 / 11 / 21, 250점, 122등, 동메달 Day 1의 만점자인 Mingyang Deng이..

IOI 2021 Day 1 대회가 종료되었다. 올해 대회의 개최지는 싱가포르지만, COVID-19로 인하여 현장 대회는 취소되었다. 대회는 모두 온라인으로 진행되며, 한국 학생들은 서울에서 모여서 감독 하에 대회를 진행하고 있다. 한국 학생들의 성적은 다음과 같다. Day 1 기준이고, Day 2 점수를 감안하지 않았음을 유념하라. 반딧불, 100 / 67 / 70, 237점, 7등 - 11등 송준혁, 38 / 37 / 100, 175점, 28등 - 29등 장태환, 11 / 37 / 70, 118점, 71등 - 100등 최서현, 100 / 9 / 5, 114점, 102등 Day 1 만점자는 중국의 Mingyang Deng이 유일하다. 전체적으로 예년에 비해서 난이도는 어려운 편이다. 점수판을 보았을 때 ..

방향 그래프 $G$ 에 대해서, $G$ 의 위상 정렬 $O: V \rightarrow [n]$ 은 모든 간선 $u \rightarrow v$ 에 대해서 $O(u) < O(v)$ 가 성립하는 순열로 정의된다. $G$ 의 위상 정렬이 존재하기 위해서는 $G$ 가 사이클이 없어야 한다는 사실이 잘 알려져 있다 (Directed Acyclic Graph, DAG). 방향 그래프에 사이클이 없다면, 위상 정렬을 적용할 수 없다. 이 경우에는 그래프에 대한 강연결 컴포넌트 (SCC) 를 구해서 사이클을 하나의 정점으로 묶어주고, 이 DAG에서 위상 정렬을 적용하는 방법이 자주 사용된다. 위상 정렬과 SCC는 방향 그래프에서 사용하는 가장 기초적인 알고리즘 중 하나이며, 그 중요성에 대해서는 길게 설명하지 않겠다. ..