-
재귀 함수에 대한 이해
개요 재귀 함수는 알고리즘 문제 풀이뿐만 아니라 프로그래밍 전반에 있어 매우 중요한 기법 중 하나입니다. 여러 복잡해 보이는 문제들을 재귀 함수 하나면 손쉽게 구현할 수 있는 경우가 많기 때문에 매우 ‘강력하다’는 표현을 자주 쓰게 됩니다. 문제 풀이에서는 DFS를 구현하는 가장 기본적인 방법으로 널리 사용되기 때문에 최근에 핫한 코딩 테스트들에서도 사용 빈도가 매우 높습니다. 그러나 재귀 함수는 알고리즘 초보가 쉽게 벽을 느끼게 될 수 있는 기법이기도 합니다. 순차적으로 그냥 실행 흐름을 따라가면 되는 다른 코드들과는 달리,...
-
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 이...