-
Half Plane Intersection
소개 안녕하세요. 이번 글에서는 반평면 교집합(Half Plane Intersection)에 대해 소개해드리려고 합니다. 반평면 교집합으로 풀 수 있는 몇 가지 재미있는 문제들이 있는데, 생각보다 관련 자료가 많지 않아서 간단하게나마 정리해 보았습니다. Half Plane Intersection 반평면(Half Plane)이란, 평면 상에 하나의 직선을 그었을 때 나누어지는 각각의 영역을 말합니다. 반평면들이 여러 개 모이면 그 교집합의 형태는 아래와 같이 볼록 다각형(convex hull)이 됩니다. 그럼 대체 이 교집합을 알면 어디에 써먹을 수 있을까요? 후술하겠지만 대표적으로는 볼록 다각형의 내접원을 구하는 데 활용할 수...
-
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...