-
ainta's profile image
ainta
October 20, 2022
SAT problem의 변형과 Schaefer’s Dichotomy Theorem
Boolean Formula, SAT $(x \lor \neg y) \land (\neg x \lor z)$와 같은 식을 Boolean formula라 한다. Boolean formula의 변수(variable)는 True/False (또는 1/0이라고도 한다)의 두가지 값만을 가질 수 있다. 위 boolean formula의 variable은 $x, y, z$이다. 각 연산자에 대해 알아보면 $\lor$ 와 $\land$는 각각 logical OR(disjunction)/ logical AND (conjunction)를 나타내고, $\neg$(negation)는 NOT을 나타내는 연산자로 피연산자가 True였다면 False로, False였다면 True로 바꿔주는 역할을 한다. 식에서 각각의 항 $x, \neg y, \neg x, z$는 literal이라 한다. $x, y$와...
-
ainta's profile image
ainta
September 18, 2022
Low degree optimal polynomial의 계산기하적 접근
Optimal Polynomial 일반적으로 함수 $f(x)$와 차수 $d$가 주어졌을 때, $\lvert P(x) - f(x) \rvert$의 최댓값 를 최소화하는 $d$차 다항함수를 $f$에 대한 degree $d$의 optimal polynomial 이라 합니다. 그러나 이러한 $P$를 구해야 하는 상황에서는 보통 함수 $f$를 모르는 상태에서, $f$가 $d$차 이하의 다항식일 것이라고 가정한 후 $P$를 추측해야 하는 경우가 잦습니다. 몇 개의 $x_i$에 대해 $f$의 실험값 $y_i = f(x_i) + \epsilon_i$ 가 주어져있을 때 오차 $\max (\lvert P(x_i) - y_i \rvert)$를 최소화하는 $P$를 어떻게 구할...
-
ainta's profile image
ainta
August 21, 2022
Formal Power Series와 Operation의 빠른 계산 방법
Introduction Polynomial Ring Field $\mathbb{F}$에 대해 Polynomial Ring $\mathbb{F}[x]$는 다항식(polynomial)들의 집합으로 정의되며, 다항식들은 각 계수 $p_i$가 $\mathbb{F}$의 원소인 $p = p_0 + p_1x + … + p_mx^m$ 꼴로 표현됩니다. 여기에서 Ring이란 간단히 말해서 덧셈과 곱셈이 정의되어 있고 해당 연산들에 대해 결합법칙이 성립하고 항등원이 정의되어 있으며 덧셈에 대해서는 교환법칙이 성립하는 집합을 말합니다. Field는 여기에 0을 제외한 모든 원소에 대해 곱셈에 대한 역원이 존재하는 경우입니다. Polynomial Ring 같은 경우는 다항식의 곱셈과 덧셈으로 자연스럽게 정의됨을 알 수 있습니다....
-
ainta's profile image
ainta
July 17, 2022
IND-CCA2 Encryption schemes and Fujisaki-Okamoto transform
Introduction 암호의 안전성 암호는 수천년 전에 로마나 고대 그리스에서 사용하던 고전암호로부터 시작해 20세기 초에는 상당히 발전되어 전쟁에서 사용되기도 했으며, 그 후 현재까지 쓰이고 있는 대칭키 암호(symmetric key cryptography) 및 공개키 암호(public key cryptography)가 개발되었습니다. 현재는 그 외에도 Lattice-based cryptography 등의 여러 암호가 활발하게 연구되고 있습니다. 초창기의 암호 중 몇몇은 하나의 문자가 하나의 문자에 대응되는 형식을 띠고 있습니다. 이러한 암호의 경우 문자마다 실제 단어에 사용되는 빈도가 달라 암호문이 충분히 주어진다면 그 빈도를 파악하여 대응되는 문자를 파악하여...
-
ainta's profile image
ainta
June 20, 2022
Gomory-Hu Tree in Subcubic Time
Introduction mincut terminology 무방향 그래프 $G = (V,E)$ 의 각 edge에 대해 양의 정수 weights $w: E \rightarrow Z_{+}$ 정의되어 있다고 하자. 정점들의 집합 $S$가 $s \in S, t \notin S$를 만족할 때 $S$를 $(s,t)$-cut 이라 한다. 이 때, $S$의 weight $\delta(S) = \Sigma_{e\in E(S, V \setminus S)} w(e)$ 가 최소인 경우를 ($s$,$t$)-mincut 이라 하고, 그 weight를 $\lambda(s,t)$라 한다. Gomory-Hu Tree Gomory-Hu Tree는 모든 $(s,t)$에 대한 mincut을 encoding하는 Tree이다. 다음과 같은 두 definition으로 정의 가능하다....
-
ainta's profile image
ainta
April 19, 2022
Compressed Sensing
Introduction Compressed Sensing(CS)이란 어떠한 신호(signal)를 효율적으로 수집 및 복원하는 기법으로, 이미지 압축이나 복원, 카메라 센서 등에 사용되는 기술이다. 간단히 예를 들어 설명하자면, N개의 픽셀로 이루어진 사진을 얻기 위해서는 N번의 observation이 필요하다고 생각하는 것이 일반적이라면 CS를 이용하는 경우 훨씬 적은 측정으로도 이를 loss 없이, 또는 매우 적은 loss로 얻을 수 있다. 이 글에서는 CS 이론의 배경과 기반 및 실제 적용에 대해 간략히 살펴본다. History Nyquist-Shannon sampling theorem $f(t)$ 가 $B$ 헤르츠 이상의 주파수를 가지지 않을 때,...
-
ainta's profile image
ainta
March 20, 2022
Casual Inference and Diagram
Introduction Simpson’s Paradox 한 제약회사가 어떤 질병에 대해 치료제를 개발한 후 이 치료제가 실제로 효과가 있는지 700명의 환자들을 대상으로 실험을 진행하였다. 환자들의 3개월간 회복 경과를 지켜본 결과 아래와 같이 나타났다. 치료제 사용 치료제 미사용 남성 81/87 회복 (93%) 234/270 회복 (87%) 여성 192/263 회복 (73%) 55/80 회복 (69%) 합산 273/350 회복 (78%) 289/350 회복 (83%) 각각의 성별에 대해서는 분명 치료제를 사용한 경우에 더 회복률이 높았지만, 합산 회복률은 치료제를 사용하지 않았을 때 오히려 더 높게...
-
ainta's profile image
ainta
June 20, 2021
Perfect Graph
Perfect Graph Graph Theory에서 유명한 그래프 종류 중에 하나로 완전그래프(Complete Graph)를 꼽을 수 있을 것이다. 완전그래프는 모든 vertex 쌍 사이에 edge가 하나 존재하는 그래프이다. 그렇다면 Complete와 비슷하게 또 완전하다, 완벽하다라는 뜻을 가진 perfect 라는 형용사가 붙는 Perfect Graph는 무슨 뜻일까? 안타깝게도 Perfect Graph는 Complete Graph처럼 직관적인 종류의 그래프는 아니다. Perfect Graph에 대해 정의하기 전에 다음을 정의하자. vertex set이 $V$, edge set이 $E$인 그래프를 $G = (V,E)$ 라고 표기한다. $V’ \subset V$ 에 대해, $E’ =...
-
ainta's profile image
ainta
December 13, 2020
IOI 2020 및 SNUPC 2020 출제후기
SNUPC 2020 출제후기 SNUPC 2020에는 Div.1의 총 9문제중 절반 정도에 해당하는 4문제를 출제하였다. 재미있는 문제를 낼 수 있어서 만족스러웠다. 그리고 imeimi2000, TAMREF 등 여러 출제진 검수진들이 고생해 준 덕분에 문제 데이터와 지문의 퀄리티가 올라가서 성공적인 대회가 될 수 있었던 것 같다. 9문제 중 대부분이 자명하지 않고 아이디어를 필요로 하는 문제들이라서 아직 풀어보지 않은 분들은 시도해 보고 나서 글을 보면 좋을 것 같다. 자세한 풀이는 여기 에 있으니 여기에는 담지 않는다. A. 빈 문자열 만들기 링크...
-
ainta's profile image
ainta
December 15, 2019
Cactus graph realization of degree sequence
Degree sequence 그래프에서, Degree sequence란 undirected graph의 각 정점의 차수(degree)를 늘어놓은 수열을 말한다. Graph realization problem이란, 수열이 주어졌을 때 그 수열을 degree sequence로 갖는 그래프를 실제로 construct하는 문제를 말한다. 여기서 다루는 그래프는 self-loop나 multiedge가 존재하지 않는 simple graph이다. 어떤 Degree sequence가 주어졌을 때, 이를 만족하는 simple graph가 존재할 조건은 Erdos - Gallai theorem 으로 널리 알려져 있다. 정리 1 (Erdos - Gallai theorem). $d_1 \ge d_2 \ge … \ge d_n \ge 0$ 가 finite simple...
-
ainta's profile image
ainta
November 17, 2019
2018 ICPC world Finals C. Conquer the world와 Tree DP optimization
2018년 World Finals에서 어느 팀도 풀지 못했던 문제인 Conquer the world(https://www.acmicpc.net/problem/15691) 문제에 대한 풀이와 사용된 아이디어에 대해 간단히 소개한다. 문제 문제 자체는 굉장히 간단하다. edge마다 이동할 때 드는 cost가 있는 트리가 있고, vertex $i$에 현재 $X_i$명이 있으며 최종 상태에는 적어도 $Y_i$명이 있어야 할 때, 사용해야 하는 cost를 minimize하는 문제이다. Heavy-Light Decomposition 이미 상당히 유명해진 트릭인 heavy-light decomposition에 대해 먼저 간략히 설명하고 넘어갈 것이다. rooted tree에서 heavy edge란, vertex $v$의 자식들 중 가장 subtree의 크기가 큰(vertex...
algorithm dynamic-programming ICPC data-structure optimization
-
ainta's profile image
ainta
September 17, 2019
Counting the number of topologies on a finite set
Topology 수학에서, topological space란 다음 조건을 만족하는 집합 $X$와 $X$의 subset들의 collection $\tau$에 대해 ordered pair $ (X, \tau) $ 를 말한다. $ \phi, X \in \tau $ Any arbitrary union of members of $ \tau$ still belongs to $ \tau$. ($ \tau$의 원소들의 합집합은 $ \tau $의 원소이다) The intersection of any finite number of members of $ \tau$ still belongs to $ \tau$. ($ \tau$의 원소 유한개의 교집합은 $ \tau $의 원소이다) 이때...
-
ainta's profile image
ainta
June 17, 2019
Matroid Intersection
Matroid Intersection Recall matroid $\mathcal{M} = (S, \mathcal{I})$ 에서 $S$는 유한집합, $ \mathcal{I} \subset 2^S$ 는 독립집합(independent set)들의 collection이다. 이 때, $I$는 다음 세 가지 조건을 만족하여야 한다. $\phi \in \mathcal{I}$ $Y \subset X, X \in \mathcal{I} \Rightarrow Y \in \mathcal{I}$ $X, Y \in \mathcal{I}, \lvert X \rvert < \lvert Y \rvert$ 이면 $X + y \in \mathcal{I}$ 를 만족하는 $y \in Y \setminus X$가 존재 매트로이드는 다양한 집합에서 정의될 수 있다. 그 중 대표적인...
-
ainta's profile image
ainta
May 15, 2019
Introduction to matroid
Matroid 정의 1. matroid $\mathcal{M} = (S, \mathcal{I})$ 에서 $S$는 유한집합, $ \mathcal{I} \subset 2^S$ 는 독립집합(independent set)들의 collection이다. 이 때, $I$는 다음 세 가지 조건을 만족하여야 한다. $\phi \in \mathcal{I}$ $Y \subset X, X \in \mathcal{I} \Rightarrow Y \in \mathcal{I}$ $X, Y \in \mathcal{I}, \lvert X \rvert < \lvert Y \rvert$ 이면 $X + y \in \mathcal{I}$ 를 만족하는 $y \in Y \setminus X$가 존재 매트로이드는 다양한 집합에서 정의될 수 있다. 그 중 대표적인...
-
ainta's profile image
ainta
March 10, 2019
Perfect Elimination Ordering in Chordal Graph
개요 Chordal Graph Chordal Graph란, 길이 4 이상의 모든 simple cycle이 chord를 포함하는 그래프를 말한다. 여기서 chord란 cycle에 포함되는 edge는 아니지만 cycle에 포함하는 두 vertex를 잇는 edge를 뜻한다. 즉, 어떤 4개 이상의 vertex를 고르더라도 그 vertex들로 이뤄진 induced subgraph가 simple cycle이 되지 않는 그래프이다. 두 겹치는 구간을 edge로 연결한 Interval graph가 Chordal graph의 한 예이다. 위는 chordal graph의 예이다. 임의의 길이 4 이상인 cycle이 chord를 포함함을 쉽게 알 수 있다. 위는 chordal graph가 아닌 그래프의...