study/algorithm

    [Python] Offline Dynamic Connectivity - 동적 연결성 문제를 오프라인으로 해결하기

    그래프 문제에서, Dynamic Connectivity Problem이라고 하는 것은 다음 세 가지 쿼리를 해결하는 문제를 의미한다. 1. 두 정점 $u$, $v$ 를 잇는 간선을 추가한다 2. 두 정점 $u$, $v$ 를 잇는 간선을 제거한다 3. 정점 $u$ 에서 $v$ 로 도달 가능한지 확인한다 단순하게 1, 3번 쿼리로만 이루어진 문제이거나, 2-3번 쿼리로만 이루어진 문제라면 Disjoint-Set Union(DSU) 자료구조를 사용해서 해결할 수 있다. 간선을 추가하고 제거하면서 그와 동시에 정점 사이에 경로가 있는지 확인하려면.. 꽤나 어려울 것 같다. 이런 식의 문제를 해결하는 방법은 크게 두 가지가 있다고 생각하는데, 하나는 (내가 모르는) 자료구조나 알고리즘을 사용해서 문제를 해결하는 ..

    [Algorithm | Python] HeavyLight Decomposition (HLD)

    ㅎㄹㄷ 올려야지, 올려야지 하고 하던 걸 이제야 정리. 아직 완성되지 않았다 HeavyLight Decomposition (HLD)는 트리에서의 쿼리를 효율적으로 수행하도록 하는 테크닉이다. 다음과 같은 두 쿼리가 있다. 1. 트리의 정점 $u$ 에서 $v$ 로 가는 경로 중 가장 큰 가중치를 가진 정점을 찾는 쿼리 2. 정점의 가중치를 바꾸는 쿼리 배열에서 위 쿼리들을 처리하는 것은 간단하다. 세그먼트 트리나 펜윅 트리를 사용하면 $O(QlogN)$에 해결할 수 있다. 하지만 이는 배열이 선형인 점을 활용한 풀이법이기에, 비선형 자료구조인 트리에는 적용할 수 없다. 트리를 적당히 나눠서, 나눈 구간을 세그먼트 트리로 관리하면 어떨까? 라는 발상에서 나온 게 오늘 다룰 HeavyLight Decompos..

    [파이썬 | Python] 트라이 (Trie) 자료구조

    문자열은 항상 어렵다. KMP도 그렇고, digit으로 정렬하는 것도 그렇고, 알면 알수록 머리아파지는 분야. 그만큼 어렵게 만들면 훨씬 어렵게도 만들 수 있다는 이야기겠지. 오늘은 트라이를 공부했다. Radix tree / Prefix tree 라고도 불리는데, 한 단어의 접두사(접두어)를 모두 저장하고 있다. (해당 단어에 도달하기까지의 문자들을 저장한다) donghoon 이라는 단어를 보면, dong 도 접두사가 될 수 있고, do 도 접두사가 될 수 있다. 트라이에서는 이 단어들이 서로 포함관계에 있다는 것을 알려준다. 트라이에 "app", "ant", "apple"이라는 단어들을 저장한다고 하자. 트라이에는 지금까지의 모든 단어의 자취를 저장한다고 했다. 단어의 각 글자마다, 존재하지 않으면 새..