-
APIO 2021
APIO 2021 APIO 2021은 아시아 태평양 학생들을 대상으로 진행되는 정보 올림피아드 대회로, 국제 정보 올림피아드 (IOI) 바로 다음 순위의 권위와 중요성을 가진 국제 대회이다. 조금 늦기는 했지만 아직 APIO 2021의 문제들을 완전히 풀이한 글이 없어서 풀이를 작성한다. 문제 풀이 한 줄 요약 육각형 영역: 다각형 내부의 모든 격자점 간의 거리 합을 구하는 문제로 환원할 수 있다. 다각형의 3개의 축을 분리하여 생각하면, 각 축에 대해서 삼각분할과 비슷한 일종의 트리를 형성할 수 있고, 모든 경로가 이 트리...
-
An Automatic System to Detect Equivalence Between Iterative Algorithms
논문 링크 : https://arxiv.org/abs/2105.04684 논문 저자 : Shipu Zhao, Laurent Lessard, Madeleine Udell Introduction : Optimization Algorithms and Their Equivalence 수학적 최적화에는 문제를 해결하기 위한 다양한 알고리즘이 있습니다. 각 알고리즘은 그 형태를 통해서 우리에게 최적화에 대한 직관을 주기도 하고 훌륭한 성능으로 우리가 최적화 문제를 어떻게 해결할 수 있는지 알려줍니다. 이는 이미 작성했던 여러 글에서도 강조했던 내용입니다. 예를 들어, 단순히 smooth differentiable convex function $f$를 최소화하는 문제에는 여러 알고리즘이 있고, 특히 Accelerated Gradient Method를 기반으로 하는...
-
Introduction To Retroactivity
Table Of Contents Introduction Preliminaries Operations Partial Retroactivity Full Retroactivity Runtime General Retroactivity Specific Retroactivity Queue Deque Union-Find Priority-Queue Summary Introduction 안녕하세요, Aeren입니다! Persistent data structure는 어떤 data structure의 여러 상태를 저장하면서 임의의 상태로부터의 연산을 통해 도달한 새로운 상태를 관리할 수 있게 합니다. 이렇게 만들어진 상태들의 관계는 tree 구조룰 이루게 되죠. 이번 글에서 소개할 내용은 이와 대비되는 개념인 retroactive data structure입니다. Retroactive data structure에서 각 상태들의 관계는 line graph형태로 고정되있습니다. 그리고 어떤 상태가 연산을 통해...
-
서로 다른 수와 쿼리
개요 다음 문제를 생각해 봅시다. 수열과 쿼리 5 길이가 $N$인 수열 $A_1, A_2, \cdots, A_N$과 쿼리 $Q$개가 주어집니다. $i$번 쿼리마다 $l_i, r_i$가 주어지면, $[l_i,r_i]$ 구간에 존재하는 서로 다른 수의 개수를 구해야 합니다. ($1 \leq N \leq 10^5, 1 \leq Q \leq 10^5, 1 \leq A_i \leq 10^6, 1 \leq l_i \leq r_i \leq N$) 위 문제(이하 서로 다른 수와 쿼리 문제)는 problem solving을 하다 보면 가끔 맞닥뜨리게 되는데, 유명한 문제인 만큼 $O(N\sqrt{Q})$나 $O((N+Q)\log{N})$등의 다양한 풀이...
-
Wireless Digital Communication 2
서론 지난 글에서 아주 기본적인 (noise가 없는) Binary modulation / demodulation에 대해서 알아보고, 현재 통신 시스템에서 가장 쉽게 볼 수 있는 AWGN 채널에 대해서 간략하게 알아보았습니다. 이번 글에서는 지난 글에서 짧게 언급한 AWGN 채널에 대해 좀 더 자세히 다룰 예정입니다. 또한 AWGN 채널에서의 Binary modulation / demodulation에 대해서 데이터가 잘못 전송될 확률을 구하고, 기존 Binary에서 이를 M개의 bit로 확장시킨 M-ary modulation / demodulation에 대해서 알아보도록 하겠습니다. 본론 AWGN 채널 지난 글에서 작성한 내용을 잠깐 언급하고...