이번에도 역시 소멤에 투고한 글. ----------------------------------------------------------------------------------------------- 본 글에서는 간선이 하나씩 추가됨에 따라 SCC를 관리하는 Incremental SCC를 오프라인으로 처리하는 방법에 대해서 설명하겠습니다. Link Cut Digraph 문제를 보겠습니다. 문제를 간단하게 요약하자면 $N$개의 정점이 있고 $M$개의 간선을 추가하는 쿼리가 있을 때, 간선을 추가할 때마다 u에서 v로 가는 경로가 있고, v에서 u로 가는 경로가 존재하는 (u, v)(u < v, u != v)쌍의 개수를 구하는 문제입니다. 방향 그래프에서 u에서 v로, v에서 u로 갈 수 있다는 것은 ..
Compressed Trie (압축 트라이)
삼성 소프트웨어 멤버십에 투고한 글. 본 글에는 차마 너무 저렴한 어휘라서 담지 못했지만 정말 날먹이 가능한(..) 기법인듯 하다. 뭔가 자료가 있는 것 같으면서도 PS에 관련된 자료는 전무한 거 같아서 (특히 한글은) 작성했다. 나도 뭐 어디서 검색해서 알게된 것은 아니고 NYPC 2019 예선 풀다가 찾은 풀이였는데 그 이후로도 종종 써먹어서 그냥 글로 작성했다. 본격적으로 시작 서론 본 글에서는 트라이를 압축하여 트라이의 깊이를 $O(\sqrt (\sum \vert S \vert))$로 만드는 기법에 대해 설명하고자 합니다. 해당 방법은 트라이와 라빈-카프 알고리즘에 대한 선행 개념이 필요합니다. 해당 개념을 모르는 사람들을 위해 아래에 간략하게 설명하겠습니다. 트라이는 접두사 트리로, 어떤 문자열..
