-
접미사 트리 (파트 1: 정의와 응용)
이 글은 트라이(trie) 자료구조에 대한 배경지식을 전제로 합니다. 부분문자열에 대한 다양한 문제를 선형 시간에 해결할 수 있는 접미사 트리 자료구조를 소개합니다. 이론 및 구현은 쉽지 않지만, 여러 문자열 문제들을 자명하게 만들거나 더 어려운 문자열 문제들을 해결하는 데 유용하게 쓸 수 있습니다. 문자열 $S$의 길이를 $m$이라고 하고, $i$번째부터 $j$번째까지 글자로 이루어진 부분문자열을 $S[i..j]$로 표기하겠습니다. 접미사 트라이 먼저, $S$의 모든 접미사로 이루어진 트라이를 생각해 봅시다. 이를 접미사 트라이(suffix trie)라고 합니다. 예를 들어 아래는 문자열 banana에 대한 접미사...
-
압축 트라이 (Compressed Trie)
서론 본 글에서는 트라이를 압축하여 트라이의 깊이를 $O(\sqrt (\sum \vert S \vert))$로 만드는 기법에 대해 설명하고자 합니다. 해당 방법은 트라이와 라빈-카프 알고리즘에 대한 선행 개념이 필요합니다. 해당 개념을 모르는 사람들을 위해 아래에 간략하게 설명하겠습니다. 트라이는 접두사 트리로, 어떤 문자열 집합의 prefix를 관리하는 자료구조입니다. 예를 들어 문자열 집합이 {“baby”, “bank”, “be”, “bed”, “box”, “dad”, “dance”}라면 이 집합을 표현한 트라이는 아래 그림과 같습니다. 이 때 붉은색 테두리는 여기서 끝나는 문자열이 존재한다는 것을 의미합니다. 이를 앞으로 valid한 노드라고...
-
'틀렸습니다'를 받지 않기 위한 팁
개요 이전 글들에서 시간 복잡도를 고려한 코드 설계 전략과 PS에서의 런타임 에러와 디버깅에 대해 각각 다루어 보았습니다. ‘시간 초과’와 ‘런타임 에러’는 모두 오답 판정 중 특수한 경우에 해당하기 때문에 코드의 어떤 부분에 초점을 맞추어 디버깅을 해야 할지가 비교적 명확하고, 문제가 될 수 있는 유형도 어느 정도는 제한적이고 빈번히 발생하는 패턴들이 존재합니다. 특히 ‘런타임 에러’의 경우에는 백준 온라인 저지에서 얼마 전부터 런타임 에러의 종류를 공개하기 시작해서, 문제의 원인을 파악하기가 이전보다 훨씬 용이해졌습니다. 오답 판정 중 가장...
-
비지도 방식으로 GANs의 이미지 생성을 조작하는 방법
소개 GANs는 이미지 생성이나 스타일 변화 테스크에서 굉장한 성능을 보여주고 있습니다. 특히, StyleGAN, BigGAN과 같은 최신 모델은 이미 실제와 구분이 힘들정도로 자연스러운 이미지를 생성합니다. 유저가 아웃풋 이미지를 원하는 형태로 조절하는 연구 또한 많이 진행되었으나 대부분 추가적인 라벨을 사용해서 모델을 학습하는 것에 초점을 맞췄었습니다. GANs의 해석 가능성에 대한 연구가 활발해지면서 각 특징을 조작하는 변수가 잘 구분되도록 학습하는 테스크인 disentanglement learning이 주목받게 됩니다. InfoGAN, beta-VAE 등이 대표적인 모델로 비지도 방식으로 생성 모델을 학습하면서 출력 결과의 중요한 특징들을...
-
Dynamic MSF with Subpolynomial Worst-case Update Time (Part 3)
Dynamic MSF with Subpolynomial Worst-case Update Time (Part 3) Chapter 4: Continued 4.2. Contraction 4.2.1 Properties of Contraction Lemma 4.2를 사용하여 우리는 Non-tree edge의 개수가 작은 Decremental MSF 알고리즘으로 문제를 환원하였다. 이제 이를 Edge의 개수가 작은 Decremental MSF 알고리즘으로 다시 환원한다. 다행이도, 이 부분은 Competitive Programming에서 익숙한 내용이라서 배경 지식이 있다면 빠르게 이해할 수 있다. Definition 4.11. (Connecting Paths). 트리 $T = (V, E)$ 와 터미널의 집합 $S \subseteq V$ 가 있을 때, $P_{S}(T)$ 는...