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
Minimum Spanning Tree 알고리즘의 증명
MST를 알고 있고, 크루스칼과 프림을 알고 있지만 그냥 쓰고있지 않은가? 이 글을 통해서 "왜 돼?" 에 대한 해답을 찾을 수 있었으면 좋겠다. 그래프가 주어졌을 때, 모든 노드를 연결하는 트리를 Spanning Tree라고 하고, 이 중에서 가장 간선의 가중치의 합이 낮은 트리를 Minimum spanning tree(이하 MST)라고 한다. MST를 만드는 방법으로는 Prim, Kruskal 알고리즘으로 두 가지가 있으며, 각각 $O(ElogV), O(ElogE)$ 가 소요된다. (그래프가 dense할 수록 $E$ 는 $V^2$ 에 가까워지며, $O(ElogE) = O(ElogV^2) = O(2ElogV)$ 로 비슷한 시간복잡도를 가진다.) 두 알고리즘 모두 그리디로 진행하며, 두 알고리즘의 증명 ..
→2022.10.11
study/algorithm
[algorithm] 수학적 귀납법을 사용해 재귀를 증명하기
0. 글을 쓰는 이유와 잡다한 이야기 이번 학기에는 이라는 과목을 수강한다. 나는 알고리즘을 통한 문제해결(Problem Solving)에 관심이 많아서 혼자 여러 알고리즘들을 공부해왔다. 군대를 다녀오기 전, 새내기 시절에는 동아리 내에서 알고리즘 대회를 열어 문제를 출제하기도 했었다. 코로나의 여파가 가시질 않아 이번 학기도 대부분의 과목들이 비대면으로 진행했고, 알고리즘 또한 그랬다. 1주차 강의밖에 듣지 않았지만, 느낀 게 꽤나 많다. 나의 알고리즘 공부법이 완벽하게 틀렸다고 할 수 있을 정도였다. 여러 알고리즘 유형의 문제들을 풀어왔지만, 문제에 대한 정당성이나 증명을 러프하게 넘기거나, 흔히들 말하는 Proof by AC (맞았습니다로 증명하기)로 퉁쳤기 때문이다. 지금 생각해 보면 굉장히 나..
→2022.09.02
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
• 다음