-
Codeforces Round #578 개최 후기
개요 Codeforces Round #578 (Div. 2) Announcement Editorial 지난 8월 11일, 현재 세계 최대 규모의 사설 프로그래밍 대회 사이트인 Codeforces에서 hyunuk (aka. jwvg0425) 님과 제가 공동 개최한 Codeforces Round #578 (Div. 2)가 열렸습니다. 이전까지 소규모 대회 개최에 출제자나 검수자로 참여해보기는 했었으나, 백 명 내외가 참가했던 기존 대회들과는 달리 무려 만 명이 넘게1, 그것도 전세계에서 참가하는 대회였기에 본격적이었습니다. 이 글에서는 이 라운드가 개최되기까지의 전 과정을 돌이켜보며 생각을 서술하고, 문제별로 간단한 솔루션과 함께 코멘트를 남겨보려고 합니다. 역사...
-
$O(N^{1/4 + ε})$ 시간 복잡도에 소인수 분해하기
$O(N^{1/4 + \epsilon})$ 시간 복잡도에 소인수 분해하기 소인수 분해 문제는 합성수가 주어졌을 때 이를 소수들의 곱으로 표현하는 방법이다. 대한민국 초등학교 교과 과정에도 있을 정도로 잘 알려진 이 문제는 계산적인 관점에서 보았을 때 매우 어려운 문제 중 하나이다. 소인수 분해는 입력 크기에 대해 (숫자의 크기를 $N$ 이라고 하면, $\log N$ 에 대해) 다항 시간 복잡도 알고리즘이 존재하지 않는다. 이러한 “어려운” 성질 때문에 소인수 분해는 다양한 암호 알고리즘에 자주 사용된다. 소인수 분해는 간단한 $O(N^{1/2})$ 알고리즘이 존재하지만, 이보다...
-
비트 연산을 활용하여 두 문자열의 LCS 빠르게 구하기
이 포스트에서는 두 문자열 $A[1..n]$, $B[1..m]$의 최장 공통 부분 수열(이하 LCS)을 $O(nm/w)$ 시간에 구하는 방법에 대해 서술합니다. Lloyd Allison, Trevor I. Dix의 A bit-string longest-common-subsequence algorithm을 보고 작성한 글입니다. 일반적으로 LCS를 구하는 방법 $T[i][j]$를 $A[1..i]$와 $B[1..j]$의 LCS 길이로 정의하면, 아래와 같은 점화식이 성립한다는 사실이 잘 알려져 있습니다. \[T[i][j] = \begin{cases} 0 & \text{if $i=0$ or $j=0$} \\ T[i-1][j-1]+1 & \text{if $A[i] = B[j]$} \\ \max(T[i-1][j],T[i][j-1])& \text{otherwise} \end{cases}\] $0 \le T[i][j] - T[i][j-1] \le 1$이므로, 새로운...
-
Shellcoding and Bitflip Conjecture
서론 이번에 DEF CON CTF 2019에 팀 SeoulPlusBadass로 다녀왔습니다. 결과 링크 대회의 대부분의 문제가 프로그램의 취약점을 찾아서 익스플로잇하는 Pwnable 문제였는데, 그렇지 않은 문제는 ropship, DOOOM, bitflip conjecture 세 문제였습니다. 그 중에서도 Bitflip Conjecture는 흥미로운 Shellcoding 문제여서 이번에 공유하고자 합니다. Bitflip Conjecture Bitflip Conjecture는 X64 Assembly로 작성된 Binary를 전송하는 문제입니다. 자세한 것은 문제에 접속하면 나오는 메시지를 살펴봅시다: =============================================================================== Definition: A snippet of assembly code is `N-Flip Resistant` if its output remains constant (i.e., it produces the...
-
Suffix Automaton 구현과 그 응용
목차 1. 개요 2. 구현 3. 응용 4. 문제풀이 5. 마무리 6. 참고자료 개요 이 포스트를 쓰며 이번 포스트에서 살짝 양심고백을 한다면, 원리를 100% 이해하지 못하고 그 구현과 구현체만을 응용하는 것을 다루는 것을 리뷰하려고 합니다. Suffix Automaton의 구현과 동작이 모두 $O(N)$에 이루어지기 때문에 그 효율성 때문에 사용만 가능하다면 매우 유용할 것 입니다. Suffix Automaton의 원리를 전부 이해하고 구현한다면 참 좋겠지만, 아직 몇가지 소정리에 대해서 더 공부해야 이해가 제대로 될 것 같아서 구현방법만 집중적으로 설명하고, 응용에...