Algorithm

study/algorithm
[Algorithm | Python] HeavyLight Decomposition (HLD)
ㅎㄹㄷ 올려야지, 올려야지 하고 하던 걸 이제야 정리. 아직 완성되지 않았다 HeavyLight Decomposition (HLD)는 트리에서의 쿼리를 효율적으로 수행하도록 하는 테크닉이다. 다음과 같은 두 쿼리가 있다. 1. 트리의 정점 $u$ 에서 $v$ 로 가는 경로 중 가장 큰 가중치를 가진 정점을 찾는 쿼리 2. 정점의 가중치를 바꾸는 쿼리 배열에서 위 쿼리들을 처리하는 것은 간단하다. 세그먼트 트리나 펜윅 트리를 사용하면 $O(QlogN)$에 해결할 수 있다. 하지만 이는 배열이 선형인 점을 활용한 풀이법이기에, 비선형 자료구조인 트리에는 적용할 수 없다. 트리를 적당히 나눠서, 나눈 구간을 세그먼트 트리로 관리하면 어떨까? 라는 발상에서 나온 게 오늘 다룰 HeavyLight Decompos..
→2022.06.22
study/algorithm
[파이썬 | Python] 트라이 (Trie) 자료구조
문자열은 항상 어렵다. KMP도 그렇고, digit으로 정렬하는 것도 그렇고, 알면 알수록 머리아파지는 분야. 그만큼 어렵게 만들면 훨씬 어렵게도 만들 수 있다는 이야기겠지. 오늘은 트라이를 공부했다. Radix tree / Prefix tree 라고도 불리는데, 한 단어의 접두사(접두어)를 모두 저장하고 있다. (해당 단어에 도달하기까지의 문자들을 저장한다) donghoon 이라는 단어를 보면, dong 도 접두사가 될 수 있고, do 도 접두사가 될 수 있다. 트라이에서는 이 단어들이 서로 포함관계에 있다는 것을 알려준다. 트라이에 "app", "ant", "apple"이라는 단어들을 저장한다고 하자. 트라이에는 지금까지의 모든 단어의 자취를 저장한다고 했다. 단어의 각 글자마다, 존재하지 않으면 새..
→2021.05.17

• 이전
• 1
• 다음