PS 썸네일형 리스트형 Aho–Corasick algorithm Aho–Corasick 알고리즘은 특정 문자열에 패턴이 존재하는지를 확인하는 알고리즘이다. 패턴들의 길이의 합을 $m$, 확인하고 싶은 문자열을 $n$이라고 하면 $O(n+m)$의 시간에 패턴이 존재하는지 확인할 수 있다. 자세한 설명은 www.slideshare.net/ssuser81b91b/ahocorasick-algorithm를 참고하자. class AhoCorasick { private: struct node { node* child[26]{}; node* failure = nullptr; node* output = nullptr; } root; void deallocate(node* p) { for (auto q : p -> child) { if (q) { deallocate(q); } } de.. 더보기 BOJ 18826 A+B (MC) 놀랍게도 이 문제는 숏코딩이 가능하다. 제출하라는 512×256×512 크기의 Anvil 파일은 사실 16×256×16 크기의 Chunk 1024개로 이루어져 있다. 구조가 알려져 있으므로 직접 Anvil 파일을 최적화하는 방법도 있겠지만, 다행히 Anvil 파일에서 필요없는 Chunk를 날려버리는 mcaselector라는 툴이 있다. 이를 이용해서 1개의 Chunk 안에 코드를 구현하고 필요없는 1023개의 Chunk를 지워버리면 굉장히 작은 파일으로 제출할 수 있다. 먼저 에디토리얼을 읽고 오면 A and not B를 계산하는 A ? B만을 이용해서 4 bit adder를 구현해야 한다는 사실을 알 수 있다. 이때 중계기의 특성상 B가 A보다 먼저 도착해야 하지만, 괜히 시간을 다르게 해놓으면 헷갈리.. 더보기 Hopcroft–Karp bipartite matching algorithm Hopcroft–Karp 알고리즘은 이분 그래프에서 최대 매칭을 $O((V+E)\sqrt{V})$에 구하는 알고리즘이다. 아이디어는 다음과 같다. 정점의 집합 $X$, $Y$가 있고, 이분그래프 $G = (X \cup Y, E)$의 어떤 매칭 $M$이 있다고 하자. (매칭은 간선의 집합이라고 보고, 자명히 $M \subset E$ 다.) 이때 $X$에 속하면서 아직 매칭되지 않은 정점에서 출발해, $E-M$에 속한 간선과 $M$에 속한 간선을 번갈아 가면서 $Y$에 속하면서 아직 매칭되지 않은 정점으로 도착하는 단순 경로를 확장 경로(augmenting path)라고 한다. 이때 어떤 매칭인지 언급해야 할 필요가 있을 경우 M-확장 경로(augmenting path with respect to M)라고 .. 더보기 이전 1 다음
