-
rth Root Extraction
서론 이번에 CTF 문제를 풀면서 한 가지 특이한 문제를 보게 되었습니다. 문제의 핵심 부분은 다음과 같았습니다. 소수 $p$와 $\gcd(p-1,r)\neq1$인 $r$에 대해서 $m^r\text{mod}\ p$가 있을 때 $m$을 구할 수 있는가? 일반적으로 $\gcd(p-1,r)=1$이라면 $p-1$에 대한 $r$의 역수 $r^{-1}$을 구한 뒤 $(m^r)^{r^{-1}}$을 계산하면 $m$을 구할 수 있습니다. 하지만 그렇지 않은 경우에 대해서는 본 적이 없었기 때문에 검색하는데 시간을 꽤 들이게 되었습니다. 저는 한 논문을 보고 구현했지만, 일반적으로 Adleman-Manders-Miller Root Extraction이라는 Method를 사용한다는 것을 CTF가 끝난 뒤 알게 되었습니다....
-
'촛불과 그림자' 해결 일지
혹시 기하 문제를 좋아하시나요? Problem Solving에 나오는 어려운 기하 문제는 다양한 예외처리와 기하 문제 특유의 방향성 때문에 인해 일반적으로 기피대상입니다. 우연히 맞닥뜨린 문제인 BOJ 18190번 ‘촛불과 그림자’도 악명 높은 기하 알고리즘 문제로, solved.ac에서 Ruby V로 평가되는 고난이도의 문제입니다. 알고리즘 구상부터 해결까지 대략 일주일 정도 걸린 시련의 길을 반면교사로 삼고자 이렇게 글을 쓰게 되었습니다. 이후엔 촛불과 그림자 문제의 상세한 아이디어와 풀이가 나오므로 유의하시기 바랍니다. ‘촛불과 그림자’란? 해결 일지 1월 14일: 구상 1월 15일: 첫 제출에서 59%까지...
-
시간 복잡도를 고려한 코드 설계 전략
개요 알고리즘 문제에는 여러 가지 제한이 주어집니다. 여기에는 입력으로 주어지는 값의 범위, 그 값들이 가지는 성질 등의 조건도 있지만, 대부분의 경우 메모리 제한과 시간 제한이 같이 주어집니다. 많은 문제들에서는 이 제한을 크게 고려하지 않고도 답을 찾아내는 로직만을 생각하여 코드로 구현하면 통과할 수 있지만, 일부 문제에서는 시간 제한 때문에 직관적인 해결책으로는 통과할 수 없는 경우도 존재합니다. 따라서 알고리즘 문제를 풀 때에는 코드를 작성하기 전후로 로직과 코드의 시간 복잡도를 계산하는 것이 중요합니다. 시간 복잡도는 알고리즘을 공부할 때...
-
#P-완전성, 그리고 완전 매칭의 개수
이 글은 튜링 기계와 NP-complete에 대한 기본 배경지식을 전제로 합니다. 서론 이분 그래프가 주어졌을 때 최대 매칭을 구하는 문제는 알고리즘 문제 풀이에서 잘 알려져 있습니다. 심지어 일반적인 그래프가 주어져도 최대 매칭을 다항 시간에 구할 수 있습니다. 그러므로 완전 매칭이 존재하는지도 같은 방법으로 구할 수 있습니다. 하지만 완전 매칭의 개수를 구하라고 하면 어떻게 될까요? 카운팅 문제와 #P-완전 NP-완전성을 이야기할 때는 문제가 결정 문제로 한정됩니다. 예를 들어 최대 클릭 문제는 “가장 큰 클릭은 무엇인가?”가 아니라 “크기가 $k$...
-
Dynamic MSF with Subpolynomial Worst-case Update Time (Part 2)
Dynamic MSF with Subpolynomial Worst-case Update Time (Part 2) Chapter 3. Continued Proof of Lemma 3.4: The Algorithm. $G_0, \alpha_0, l$ 을 Lemma 3.4의 입력이라고 하자. 알고리즘은 $l + 1$ 개의 레벨 로 그래프를 관리한다. 각 레벨은 간선의 부분집합을 관리하며, one-shot expander pruning algorithm을 호출한다. 레벨이 깊을 수록 (숫자가 클 수록) one-shot expander pruning algorithm의 호출 횟수는 많아지며, 반대로 간선의 개수는 적어진다. 정확히 어떠한 원리인지는 후술하고, 아래 필요한 정의를 나열한다. $\delta = \frac{2}{l}$ 이다. $n,...