-
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’ =...
-
SCLI Framework and its Applications on Minimax Problems
Introduction Machine Learning, Artificial Intelligence의 가장 기본적인 구조는 주어진 데이터에 대한 loss function을 만들고, 이를 최소화하는 것입니다. loss function $f$를 design 했다면, 이 $f$를 최소화하는 것은 최적화 알고리즘의 영역에 들어오게 됩니다. 특히, ML/AI 분야에서는 $f$를 최소화하기 위하여 그 gradient $\nabla f$를 사용하는 gradient-based optimization을 주로 사용합니다. 이러한 환경에서, 최적화 알고리즘을 연구하는 사람들이 자연스럽게 최적화 알고리즘에 대하여 주로 관심을 가지게 되는 정보는 크게 다음과 같습니다. $f$에 대한 특정 조건이 주어졌을 때, 주어진 알고리즘이 얼마나 빠르게 최적해로...
-
Parallel Binary Search
이 게시글은 이분 탐색에 대한 지식을 필요로 합니다. 그리고 union-find, segment tree 자료구조에 대해 알고 있으면 좋습니다. 아래 문제를 봅시다. 제한된 메모리(링크) 길이 $N$의 배열 $A$에서, $q$번째로 작은 원소를 구하는 쿼리를 여러 번 해결하는 문제입니다. 하지만, 문제 지문에 나와 있듯이, 이 문제의 메모리 제한은 4MB로 $A$에 대한 메모리를 할당할 수 없습니다. 하나의 쿼리에 대해 해결해 봅시다. $f(a) =$ 배열 $A$에서 $a$ 이하인 수의 개수라고 합시다. $f(a) \geq q+1$인 경우, $q$번째로 작은 원소는 $a$ 이하입니다. 함수...
-
Gauss-Jordan Elimination
개요 Gauss-Jordan Elimination(가우스 조던 소거법)은 미지수 $x_1$, $x_2$, $…$, $x_m$에 대한 $n$개의 일차방정식으로 구성된 연립일차방정식을 푸는 방법입니다. 해가 존재하는지, 존재한다면 유일한지 판단하고 그 중 하나의 해를 구할 수 있습니다. 연립일차방정식과 행렬 다음과 같은 연립 일차방정식을 생각해봅시다. \[a_{11}x_1 + a_{12}x_2 + ... + a_{1m}x_m = b_1 \\ a_{21}x_1 + a_{22}x_2 + ... + a_{2m}x_m = b_2 \\ \vdots \\ a_{n1}x_1 + a_{n2}x_2 + ... + a_{nm}x_m = b_n\] 이 때, 각 일차방정식의 계수들과 미지수, 상수항을 묶어...
-
Data Structure For Range Mode Query
Table Of Contents Introduction Hardness Result First Method Second Method Third Method Final Method Introduction 안녕하세요, Aeren입니다! Competitive programming을 해본 적 있는 분이라면 range sum query, range minimum query 등등의 다양한 range query문제를 접해보셨을 것입니다. 많은 range query problem들은 linear memory만으로 sublinear time query를 가능하게 해주는 data structure가 존재합니다. 이번 글에서는 비슷한 맥락의 range mode query 를 해결하는 linear memory data structure에 대해 알아 볼 것입니다. 이 글은 다음 논문을 바탕으로 작성되었습니다. Array 혹은 multiset...