-
두 번째 주의 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 : 작성 중
-
K-D Tree
k-d트리는 다차원의 점들(자료들)을 저장하기 위한 자료구조입니다. 알아보기 전에 먼저 저보다 훨씬 잘 설명해둔 위키피디아 페이지를 소개하겠습니다. (링크) 그냥 여기만으로 이해하는 게 훨씬 편할 수도 있습니다. 개요 설명하자면 k-d 트리는 모든 노드가 k차원 점인 이진 트리입니다. 모든 리프 노드는 공간을 반평면의 두 부분으로 나누는 분할 초평면을 만드는 것으로 생각할 수 있습니다. 이 초평면의 왼쪽은 그 노드의 왼쪽 부분 트리를 나타내고 오른쪽은 오른쪽 부분 트리를 나타냅니다. 초평면은 k차원 중 하나의 차원축에 수직적이어야 합니다. 그러니 예를 들어 x=3을...
-
해싱으로 문자열 문제 날로 먹기
Intro ACM-ICPC 등에서 주로 출제되는 문자열 문제는 일반적으로 KMP, Suffix Array, Trie, Aho-Corasick 등의 자료구조나 알고리즘을 사용해서 해결하는 것이 정해인 경우가 많습니다. 하지만, 그 중 많은 문제는 정해를 사용하지 않고도 운에 맡기기만 한다면 비교적 쉽게 해결 가능합니다. 이럴 때 사용하는 기법이 바로 해싱(Hashing)입니다. 해싱은 문자열을 어떤 숫자와 1대1로 대응시킴으로서, 전처리 이후 문자열의 비교와 검색을 사실상 $O(1)$ 에 가능하게 해 줍니다. 이 해싱의 강력한 특징을 이용하면, 문자열 문제들을 날로 먹을 수 있는 경우가 꽤 있습니다. 이...
-
번사이드 보조 정리
첫 번째 주의 AlgoShitPo에서 ahgus89의 지목을 받아 Burnside’s Lemma를 작성하게 된 justiceHui입니다. 서론 번사이드 보조 정리는 원순열 등의 경우의 수를 구하는 문제에서 자주 나오는 정리입니다. 공부하기 위해 책을 보거나 검색을 하면, $\displaystyle \frac {1}{n}\sum_{k=1}^{n} c(k)$같은 공식만 나와있거나 Group Theory가 튀어나오는 경우가 대부분입니다. 저는 고등학교에 재학중인 학생으로써, 고등학교 수준에 맞춰 번사이드 보조 정리의 아이디어를 소개하는 것에 초점을 맞추도록 하겠습니다. 문제 1 위 그림처럼 구슬 4개로 구성된 목걸이가 있을 때, 각 구슬을 빨간색 혹은 파란색으로 색칠하는 경우의...
-
Simplex
첫 번째 주의 AlgoShitPo에서 Ryute의 지목을 받아 Simplex Method를 작성하게 된 ahgus89입니다. 서론 Simplex Method는 Linear Programming(LP) 문제를 해결하는 방법 중 하나입니다. LP는 무엇일까요? 위키백과에 따르면, “주어진 선형 조건을 만족시키면서 선형인 목적 함수를 최적화하는 문제” 라고 합니다. 중학교 때 배운 부등식의 영역 문제를 생각해봅시다. 다음과 같은 문제가 있습니다. 물건 $P$, $Q$를 만들 예정인데, 재료 $A$, $B$가 각각 $100g$씩 있습니다. $P$ $1g$를 만들 때는 $A$를 $1g$, $B$를 $2g$ 사용하며, $Q$ $1g$를 만들 때는 $A$를 $3g$, $B$를...