study/algorithm

study/algorithm
Longest Increasing Subsequence (LIS)를 NlogN에 구하기
최장 증가 부분 수열이라고 불리는 Longest Increasing Subsequence는 $O(NlogN)$ 에 구할 수 있다. 많은 블로그에서 이분 탐색을 활용한다라는 해결책을 제시하는데, 해당 풀이를 도출해나가는 과정을 자세히 작성하고자 한다. 알고리즘 강의를 들으며 정리한 내용으로, 오류가 있을 수 있습니다. 발견하신다면 댓글로 알려주시면 감사하겠습니다 🙌 0. Longest Increasing Subsequence LIS는 주어진 수열에서 가장 긴 증가하는 부분 수열이다. 주어진 수열을 $S$ 라고 하고, LIS를 $L$ 라고 하자. 이때, $L$ 의 원소들이 $S$에서 연속적으로 존재해야할 필요는 없다. LIS는 어떻게 구해야 할까? 1. Naive 간단히 생각하면, 모든 경우의 수를 다 따져..
→2022.11.03
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) 자료구조를 사용해서 해결할 수 있다. 간선을 추가하고 제거하면서 그와 동시에 정점 사이에 경로가 있는지 확인하려면.. 꽤나 어려울 것 같다. 이런 식의 문제를 해결하는 방법은 크게 두 가지가 있다고 생각하는데, 하나는 (내가 모르는) 자료구조나 알고리즘을 사용해서 문제를 해결하는 ..
→2022.08.01
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
• 다음