-
IOI 2021
IOI 2021 대회가 종료되었다. 올해 대회의 개최지는 싱가포르지만, COVID-19로 인하여 현장 대회는 취소되었다. 대회는 모두 온라인으로 진행되며, 한국 학생들은 서울에서 모여서 감독 하에 대회를 진행하고 있다. 이 글에서는 해당 대회에 출제된 문제들을 하나 하나 풀어보고, 그 풀이를 소개한다. IOI에는 다양한 문제가 나오기 때문에 모든 풀이를 하나의 주제로 요약할 수는 없다. 고로 각 풀이의 핵심 키워드를 아래에 정리하였다. 구현한 풀이는 모두 https://github.com/koosaga/olympiad/tree/master/IOI 에서 찾을 수 있다. 문제 풀이 한 줄 요약 candies: 수열에 직접 쿼리를 적용하는...
-
오일러 지표와 문제 풀이
평면 연결 그래프에서 $V$와 $E$를 각각 정점과 간선의 집합 $f$를 면의 개수라고 할 때, $|V|-|E|+f=2$라는 공식이 성립하고 우리는 흔히 이를 오일러 지표라고 부릅니다. 여기서 면은 outer face, 즉, 무한히 바깥으로 뻗어나가는 면을 포함합니다. 위의 그래프에서도 이 식이 성립함을 관찰하실 수 있습니다. 평면 연결 그래프 $G$에서 $|V|-|E|+f=2$라는 사실을 귀납법을 이용하여 증명해봅시다. 우선 임의의 트리는 항상 $|V|-|E|=1$ 이므로, 이 공식이 성립함을 쉽게 보일 수 있습니다. 만약 그래프가 트리가 아닌 경우, 임의의 사이클이 존재하고. 사이클을 구성하는 임의의 간선은...
-
람다 표현과 처치 인코딩(1)
람다 표현(Lambda Expression)이란? 간단히 설명하자면, 람다 표현은 어떤 함수를 이름 없이 표현하는 방식이라 할 수 있습니다. 이런 특징으로 인해, 람다 표현은 종종 익명 함수(anonymous function)라고 불리기도 합니다. ‘이름 없이 표현한다’는 의미를 좀 더 와닿게 하기 위해, 한 가지 예시를 들어보도록 하겠습니다. 만약 $x$를 받아서 $x+1$을 내놓는 함수를 표현하고 싶다면 어떻게 해야 할까요? 보통의 경우, 아래와 같이 수학적인 표현법을 사용할 수 있습니다. $ f(x) = x + 1 $ 눈치채셨을지도 모르지만, 어느새 이 함수에는 $f$라는 이름이...
-
Fast Polygon Triangulation
Table Of Contents Introduction Preliminaries Degeneracy Strict Total Order Monotone Polygon Montone Polygon Triangulation Example Polygon Triangulation Boundary Vertex Classification Sweepline Events Example Implementation Introduction 안녕하세요, Aeren입니다! Polygon triangulation은 classical한 computational geometry problem중 하나로, 어떤 simple polygon의 boundary가 counterclockwise하게 주어질 때, triangulation을 찾는 문제입니다. 이번 글에서 소개할 내용은 $N$을 polygon의 vertex 갯수라고 할 때 $O(N \log N)$시간 안에 위 문제를 해결하는 알고리즘입니다. 참고로 이 문제는 $O(N)$시간 안에 해결 가능함이 알려져 있습니다. (참조) Preliminaries Degeneracy 이...
-
Fully Dynamic Min Cut
Fully Dynamic Min Cut 그래프의 Minimum Cut (최소 컷) 은 그래프가 연결되지 않도록 지워야 하는 간선의 최소 개수를 뜻한다. 간선에 양의 정수 가중치가 붙으면 이를 Weighted Minimum Cut 이라고 부르고, 이 때는 그래프가 연결되지 않도록 지워야 하는 간선 가중치 합의 최소를 구해야 한다. 최소 컷을 다른 말로 Edge Connectivity 라고 부르기도 한다. 연결된 (Connected) 그래프는 최소 컷이 1 이상인 그래프와 동치이고, 이중 연결 (Biconnected) 된 그래프는 최소 컷이 2 이상인 그래프와 동치이고, 삼중 연결 (Triconnected)...