-
2020년 선린인터넷고등학교 교내 프로그래밍 대회들의 풀이
작년 하반기에 선린인터넷고등학교에서 개최되는 여러 정보 경시 대회에 김준원, 권욱제님 등과 함께 출제했던 적이 있습니다. 이 대회들에는 여러 교육적인 문제가 많이 있었으나, 잘 정리된 풀이는 아직 없는 것 같아서 이 참에 정리해봤습니다. 1. 2020 선린 정보 알고리즘경시대회 문제는 https://www.acmicpc.net/category/detail/2294 에서 풀어볼 수 있습니다. A. 헛간 청약 지문을 잘 읽으면 해결할 수 있는 문제다. 정답은 $\min(N, \lfloor W/L \rfloor \times \lfloor H/L \rfloor)$ 이다. 정답이 최대 $N$ 임에 유의하여 해결해야 합니다. B. 소-난다! 비트마스킹을 이용하여 $2^N$개의...
-
testlib 사용하기
개요 testlib는 Polygon에서 프로그래밍 문제를 만들기 위한 유틸리티를 한데 모아놓은 라이브러리입니다. Generator, validator, checker 및 interactor 제작에 공통적으로 사용되며, 신뢰도 높은 랜덤 함수, 안정성 있으며 정규표현식을 지원하는 문자열 파싱, Polygon 및 채점 시스템과의 상호작용 등의 다양한 기능을 갖추고 있으며 Polygon과 GitHub 페이지에서 다양한 사용 예제들도 제공해 줍니다. 문제 출제를 위한 플랫폼 - Polygon 사용하기 글에 간단한 사용 예시가 나와있습니다. 유용한 기능을 많이 갖추고 있고 코드의 주석 또한 훌륭한 반면에 testlib에 대한 별도의 문서화는 이루어지지 않았습니다....
-
Variance Reduction Algorithms and Catalyst Acceleration
서론 본 글에서는 단순히 convex function $f$를 최소화 하는 것이 아니라, 이들의 합인 $F = \frac{1}{n} \sum_{i=1}^n f_i(x)$ 를 최소화하는 알고리즘에 대해서 알아보고, 이에 Catalyst를 적용해보겠습니다. 이와 같은 형식의 함수 $F$는 Logistic Regression 등 Machine Learning에서 등장합니다. 원래는 $F$에 추가적인 “proximal function”이 있어, $F = \frac{1}{n} \sum_{i=1}^n f_i(x) + \psi(x)$ 형태를 가지나 (예를 들어 $l_1$ regularization) 여기서는 편의상 $\psi$에 대한 논의를 생략하겠습니다. 글의 순서는 대략적으로 다음과 같습니다. $F$를 최소화하는 알고리즘이 발전한 과정의 큰 흐름에 대해서...
-
Heavy-light Decomposition With Globally Balanced Binary Trees
Table Of Contents Prerequisite Introduction Main Idea Implementation Benchmark Prerequisite Segment tree - Tutorial on cp-algorithms Heavy-light decomposition - Tutorial on cp-algorithms Introduction 안녕하세요, Aeren입니다! 다음 문제를 생각해봅시다. Monoid $(T,+)$와 $(L,+)$, left monoid action $\ast(\ast):(L,T)\rightarrow T$, tree $G=(V,E)$와 각 node의 가중치 $W:V\rightarrow T$이 주어진다. 다음 연산들을 수행하라. $u,v\in V$이 주어진다. $u$와 $v$를 잇는 유일한 path $P$에 대하여 $\sum_{w\in P}W(w)$의 값을 출력한다. $u,v\in V$와 $f\in L$이 주어진다. $u$와 $v$를 잇는 유일한 path $P$에 대하여 각 $w\in...
-
Union Find의 시간 복잡도 증명
Union Find Union Find 또는 Disjoint Set이라고 불리는 자료구조는 여러 개의 원소를 포함하고 있는 집합들을 다루는 자료구조이다. 초기에, $N$개의 원소들과 $N$개의 집합들이 만들어져 있고, 각각의 집합은 서로 다른 원소 하나씩을 가지고 있다. 이 위에 다음과 같은 두 개의 연산을 할 수 있다. Union(x, y) : 원소 x가 속한 집합과, 원소 y가 속한 집합을 합친다. Find(x) : 원소 x가 어떤 집합에 속해있는지 반환한다. 보통 x가 속해있는 집합의 대표 원소 하나를 반환한다. struct dsu { dsu() {...