-
대회/코딩 테스트용 간이 테스터 만들기
개요 프로그래밍 문제를 풀다 보면 종종 맞왜틀 (맞았는데 왜 틀려요)의 벽에 부딪히게 됩니다. 예제도 다 맞고, 열심히 생각해서 넣어본 여러 케이스들도 맞는데도 제출만 하면 틀렸다고 하고… 도무지 반례가 안 보일 때의 답답함은 말로 표현할 수가 없습니다. 연습용으로 문제를 풀 때에는 그나마 Polygon과 같은 전문 도구를 사용해서 스트레스를 돌리거나 견고하게 짜여진 테스트용 도구를 로컬에서 실행해보면서 반례를 찾을 수도 있습니다. Polygon의 사용법은 Acka1357 님의 글 문제 출제를 위한 플랫폼 - Polygon 사용하기에서 자세하게 확인할 수 있습니다. 하지만...
-
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$에 대한 특정 조건이 주어졌을 때, 주어진 알고리즘이 얼마나 빠르게 최적해로...