-
2-dimension Euclidean Minimum Spanning Tree
\[\newcommand{\PhiInsert}{\Phi_{insert}} \newcommand{\PhiDelete}{\Phi_{delete}} \newcommand{\size}{\mbox{size}} \newcommand{\capa}{\mbox{capacity}} \newcommand{\di}{D_{i}} \newcommand{\dim}{D_{i-1}} \newcommand{\zig}{\mbox{Zig}} \newcommand{\zzig}{\mbox{Zig-zig}} \newcommand{\zzag}{\mbox{Zig-zag}} \newcommand{\bf}{\mbox{Before}} \newcommand{\aft}{\mbox{After}} \newcommand{\subt}{\mbox{Subtrees}}\] Intro Minimum Spanning Tree, 우리말로는 최소 신장 트리는 잊을 만 하면 등장하는 주제 중 하나입니다. 최소 신장 트리를 구하기 위해서는 보통 두 가지 알고리즘이 사용됩니다. 하나는 크루스칼 알고리즘으로 $O(E \log E)$의 복잡도를 가지고, 나머지 하나는 프림 알고리즘으로 $O(E \log V)$의 시간복잡도를 가집니다. 하지만 이 두 알고리즘 모두 한 가지 단점을 가지고 있는데, 일단 알고리즘을 수행하려면 모든 간선을 읽어야 한다는 것입니다. 이게 왜 문제인지...
ryute's profile imageryute
2020-05-20 16:00
-
Potential Method
\[\newcommand{\PhiInsert}{\Phi_{insert}} \newcommand{\PhiDelete}{\Phi_{delete}} \newcommand{\size}{\mbox{size}} \newcommand{\capa}{\mbox{capacity}} \newcommand{\di}{D_{i}} \newcommand{\dim}{D_{i-1}} \newcommand{\zig}{\mbox{Zig}} \newcommand{\zzig}{\mbox{Zig-zig}} \newcommand{\zzag}{\mbox{Zig-zag}} \newcommand{\bf}{\mbox{Before}} \newcommand{\aft}{\mbox{After}} \newcommand{\subt}{\mbox{Subtrees}}\] Intro Potential Method가 뭘까요? Potential Method는 우리가 흔히 사용하는 Amortized 분석과 큰 연관성을 가지고 있습니다. 어떠한 자료구조의 상태가 있을 때, 그 자료구조가 잘 작동하기 위한 ‘이상적인’ 상태가 존재합니다. 하지만 일반적으로 이 이상적인 상태를 유지하는 것은 그렇게 쉽지 않습니다. 항상 자료구조를 이상적인 상태로 유지하는 것은 굉장히 많은 비용을 요구합니다. 생각해 볼 수 있는 대안은, 자료구조를 매번 갱신하는 것이 아니라 적당히 비효율적인 연산을 하다가, 한...
ryute's profile imageryute
2020-03-23 02:00
-
두 번째 주의 AlgoShitpo
참여자 ryute, justiceHui, karuna, ahgus89가 참여합니다. 주제 선정 기한: 2020-02-11 23:59까지 ryute -> karuna : eer Tree ahgus89 -> ryute : Potential Method justiceHui -> ahgus89 : dual graph of plane graph karuna -> justiceHui : O(nlogn) Algorithm for Matrix Chain Multiplication 포스팅! 기한: 2020-02-15 23:59까지 ryute : 작성 중 ahgus89 : 작성 중 justiceHui : 작성 중 karuna : 작성 중
ryute's profile imageryute
2020-02-09 03:00
-
해싱으로 문자열 문제 날로 먹기
Intro ACM-ICPC 등에서 주로 출제되는 문자열 문제는 일반적으로 KMP, Suffix Array, Trie, Aho-Corasick 등의 자료구조나 알고리즘을 사용해서 해결하는 것이 정해인 경우가 많습니다. 하지만, 그 중 많은 문제는 정해를 사용하지 않고도 운에 맡기기만 한다면 비교적 쉽게 해결 가능합니다. 이럴 때 사용하는 기법이 바로 해싱(Hashing)입니다. 해싱은 문자열을 어떤 숫자와 1대1로 대응시킴으로서, 전처리 이후 문자열의 비교와 검색을 사실상 $O(1)$ 에 가능하게 해 줍니다. 이 해싱의 강력한 특징을 이용하면, 문자열 문제들을 날로 먹을 수 있는 경우가 꽤 있습니다. 이...
ryute's profile imageryute
2020-02-09 02:00
-
첫 번째 주의 AlgoShitpo
참여자 ryute, justiceHui, urd05, ahgus89가 참여합니다. 주제 선정 기한: 2020-02-04 23:59까지 ryute -> ahgus89 : Simplex Method ahgus89 -> justiceHui : Burnside’s Lemma justiceHui -> urd05 : K-D Tree urd05 -> ryute : Introducing about the methods to replace string algorithms with hashing 포스팅! 기한: 2020-02-08 23:59까지 ryute : 해싱으로 문자열 문제 날로 먹기 ahgus89 : Simplex justiceHui : Burnside Lemma urd05 : K-D Tree
ryute's profile imageryute
2020-02-04 17:00
-
AlgoShitpo는 무슨 블로그인가요?
AlgoShitpo? AlgoShitpo (이하 알고싯포)는 알고리즘을 좋아하는 사람들이 자유롭게 모여 수다를 떠는 카카오톡 채팅방 알고리즘 #싯포에서, 블로그에 관심 있는 사람들끼리 모여 운영하는 팀 블로그입니다. 채팅방 알고리즘 #싯포는 원조인 BOJ 슬랙의 shitpost 채널을 닮아 절제되지 않고 예의 차리지 않는 특이한 분위기를 지향점으로 잡고 있습니다. 알고싯포 또한 이런 채팅방에서 갈라져 나온 만큼 굉장히 특이한 블로그 운영 방식을 가지고 있습니다. 알고싯포의 가장 큰 특징은 글을 쓰는 주제를 자신이 정하지 않는다는 것입니다. 1주일마다 돌아가면서 자신이 다른 사람의 글쓰기 주제를 지정하고,...
ryute's profile imageryute
2020-02-04 17:00