-
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) 접미사들을 사전 순으로 나열한 배열이 접미사...
-
A Topological Approach to Evasiveness
스무고개 간단한 게임을 하나 생각해 봅시다. A와 B가 게임을 하는데, 아직 결정되지 않은 $n$자리 이진수가 있습니다. A는 B에게 $i$번째 비트가 $1$인지 물어볼 수 있고, B는 이를 답해줍니다. 질문을 $n$번보다 적게 써서 이 수가 $3$의 배수인지 맞힐 수 있다면 A의 승리, 그렇지 않다면 B의 승리입니다. 물론 B는 특정 수를 정해놓고 시작해야 하는 게 아니기 때문에, 질문에 따라 얼마든지 마음속으로 답을 바꿀 수 있습니다. 누가 승리할까요? leading zero 등의 제한 조건은 없습니다. 당연하게도, 이 게임은 B의 손쉬운...
-
트리를 활용한 새로운 효율적인 수열 쿼리 알고리즘
개요 그래프란 정점과 간선으로 구성된 자료구조로, 버스 노선 설계와 같은 생활속 문제부터 다양한 학술 분야의 이론까지 폭넓게 도입할 수 있다. 트리란 그래프의 일종으로 사이클이 없으며 연결성을 가진다는 강력한 조건을 가져 알고리즘 설계에 자주 사용된다. 본 글은 수열에서 특정 조건을 만족하는 순서쌍의 개수를 세는 복잡한 쿼리를, 트리를 활용하여 효율적으로 처리하는 새로운 알고리즘을 소개한다. 본문은 아래의 내용을 부가적인 설명 없이 서술한다. 각 항목에 대하여 자세하게 서술한 좋은 글을 링크해두었다. 세그먼트 트리 (Segment Tree) Heavy-Light Decomposition...
-
XOR 관련 문제를 푸는 접근법들
들어가기 전에 XOR (bitwise exclusive or)은 대표적인 bit 연산 중 하나입니다. 다른 bit 연산인 AND,OR,NOT이 갖지 못하는 특성 때문에, PS 및 CP에서도 관련 문제가 심심치 않게 출제되곤 합니다. 하지만 문제 제목이나 지문에 XOR이 있으면 일단 긴장하거나, 기피하시는 분들도 꽤 자주 본 것 같습니다. 그래서, 이번 글에서는 이런 XOR 관련 문제들에 접근하는 방법 몇 가지를 설명해 보려고 합니다. Basic Part 본격적으로 들어가기에 앞서, XOR 연산이 가지고 있는 성질 몇 가지에 대해서 간단하게 짚고 넘어가려고 합니다. 여러...
-
Differential Cryptanalysis on 4-round DES
서론 이번 글에서는 차분 분석 (Differential cryptanalysis)가 무엇인지 간략하게 살펴보고, 4-round DES에 대한 차분 공격을 예시로 알아보고자 합니다. 본론 차분 분석 차분 분석을 간단하게 말하자면, 어떤 함수 $f$가 주어져있을 때 $x, y$ 에 대해서 $(y - x, f(y) - f(x))$ 가 일정 확률로 특정 관계성을 만족하는 것을 이용하는 분석 방법 중 하나입니다. 이렇게만 이야기하면 쉽게 와닿지 않을 것 같아서 예시를 준비해봤습니다. S-box DES, AES와 같은 암호들을 살펴보면, 대부분의 연산이 선형 계산으로 이루어져 있습니다. 즉, 어떤...