-
Factor Base를 이용한 "어려운 문제"의 속도 개선
이 글에서는 factor base를 활용한 속도 개선을 언제 사용할 수 있는지, 사용할 경우 시간 복잡도의 개선이 정확히 얼마나 일어나는지, 실제로는 얼마나 빠른지를 알아봅니다. “어려운 문제”? 이 글에서의 어려운 문제는 크게 소인수분해와 이산 로그를 일컫습니다. 소인수분해 문제는 잘 알고 계실 것입니다. 수 $N$이 주어지면, $N$을 (서로 다를 필요는 없는) 소수 $p_{1}$, $p_{2}$, $\cdots$, $p_{n}$의 곱 $N = p_{1} p_{2} \cdots p_{n}$으로 분해하라. 예를 들어 $108 = 2 \cdot 2 \cdot 3 \cdot 3 \cdot 3 =...
-
스킵 리스트
서론 다음 연산을 모두 $O(logn)$에 지원하는 자료구조가 필요합니다. x를 추가한다. x를 삭제한다. x 이상의 원소 중 가장 작은 것을 출력한다. C++에서는 std::set가 바로 이 역할을 하지만, Python에는 이런 내장 라이브러리가 없습니다. 그래서 외부 라이브러리를 쓰지 않는 한 레드-블랙 트리나 AVL 트리 등을 직접 구현해야 하는데, 트리 자료구조는 보통 rebalancing 과정이 복잡합니다. 한편, 트리의 틀을 벗어나면 스킵 리스트 (Skip List)라는 자료구조가 있습니다. “평균”이라는 말에서 추측할 수 있듯이, 랜덤을 사용한다는 특징이 있습니다. AVL 트리 등에 비해 구현이...
-
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$ 이하입니다. 함수...