-
gumgood's profile image
gumgood
July 18, 2021
Suffix Array and LCP Array
접미사(Suffix) 문자열 $s$의 $i$번째 접미사란, $s$의 $i$번째 글자부터 마지막 글자까지 포함하는 부분문자열을 뜻합니다. 예를 들어, $s=\mathsf{GATAGACA}$의 접미사를 순서대로 나타내면 다음과 같습니다. \[\begin{array}{|c|c|} \hline \mathsf{i} & \mathsf{suffix} \\ \hline \begin{array}{c} \mathsf{0} \\ \mathsf{1} \\ \mathsf{2} \\ \mathsf{3} \\ \mathsf{4} \\ \mathsf{5} \\ \mathsf{6} \\ \mathsf{7} \end{array} & \begin{array}{l} \mathsf{GATAGACA} \\ \mathsf{ATAGACA} \\ \mathsf{TAGACA} \\ \mathsf{AGACA} \\ \mathsf{GACA} \\ \mathsf{ACA} \\ \mathsf{CA} \\ \mathsf{A} \end{array} \\ \hline \end{array}\] 접미사 배열(Suffix Array) 접미사들을 사전 순으로 나열한 배열이 접미사...
-
gumgood's profile image
gumgood
May 20, 2021
Gauss-Jordan Elimination
개요 Gauss-Jordan Elimination(가우스 조던 소거법)은 미지수 $x_1$, $x_2$, $…$, $x_m$에 대한 $n$개의 일차방정식으로 구성된 연립일차방정식을 푸는 방법입니다. 해가 존재하는지, 존재한다면 유일한지 판단하고 그 중 하나의 해를 구할 수 있습니다. 연립일차방정식과 행렬 다음과 같은 연립 일차방정식을 생각해봅시다. \[a_{11}x_1 + a_{12}x_2 + ... + a_{1m}x_m = b_1 \\ a_{21}x_1 + a_{22}x_2 + ... + a_{2m}x_m = b_2 \\ \vdots \\ a_{n1}x_1 + a_{n2}x_2 + ... + a_{nm}x_m = b_n\] 이 때, 각 일차방정식의 계수들과 미지수, 상수항을 묶어...
-
gumgood's profile image
gumgood
April 18, 2021
정수 자료형으로 기하학 문제 데이터 검증하기
개요 기하학 문제가 까다로운 이유 중 하나는 실수 자료형을 쓸 때 생기는 부동 소수점 오차 때문입니다. 같은 이유로, 데이터가 문제의 조건에 맞는지 검증하는 과정 역시 쉽지 않습니다. 심지어 실수 자료형으로는 해결할 수 없는 경우도 존재합니다. BOJ 20939 달고나를 출제하면서 겪은 문제들과 해결한 과정에 대해 정리하고자 합니다. 입력 조건 문제에서 데이터 형식과 범위를 제외하고 검증해야 하는 조건들은 다음과 같습니다. 단순 다각형의 꼭짓점은 반시계방향 순서이다. 선분의 개수와 원의 개수 합이 2,000을 넘지 않는다. 세 개 이상의 선(원...