-
2-connectivity
Connectivity Problem $k+1$개 이상의 정점을 가진 그래프 $G$가 임의의 $k-1$개의 정점을 제거하더라도 남은 그래프가 connected graph를 유지한다면 그래프 $G$를 k-vertex-connected 라고 합니다. 이때 이를 만족하는 $k$ 중 가장 큰 값을 $G$ 의 vertex connectivity 라고 합니다. 비슷한 방식으로 간선의 경우도 $k-1$개의 간선을 제거하더라도 남은 그래프가 connected graph인 경우 k-edge-connected 라고 표현하고, 그중 가장 큰 $k$ 를 $G$의 edge connectivity 라고 합니다. 아래 그림은 2-vertex-connected 그래프의 예시입니다. 어떤 정점을 삭제하더라도 남은 그래프가 연결 그래프로 유지되기 때문입니다....
-
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...