-
알고리즘 문제 접근 과정
알고리즘 문제 접근 과정 알고리즘 문제 풀이를 진행하면서, 어느정도 순간에서부터는 내가 모르는 알고리즘 및 자료구조가 필요하다는 점에서 문제 풀이의 어려움을 느끼게 됩니다. 더 발전하기 위해서 다양한 내용들을 찾아서 공부하고 이를 구현하는 방법을 익히는 과정이 필요하게 됩니다. 하지만 처음 공부할 때에 실제로 제가 가장 많이 겪었던 문제, 혹은 다른 사람들이 처음 공부를 시작 하면서 어려웠던 점들에 대해 이야기를 들을 때에 공통적으로 나왔던 부분은 바로, 알고리즘과 자료구조를 알고 있어도, 해당 문제를 어떤 알고리즘과 어떤 자료구조를 사용해야 하는지...
-
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 연산이 가지고 있는 성질 몇 가지에 대해서 간단하게 짚고 넘어가려고 합니다. 여러...