-
랜덤으로 문제 풀기
서론 알고리즘 문제를 풀 때 랜덤을 사용해 문제를 해결하는 경우가 있습니다. 최악의 시간 복잡도와 평균 시간 복잡도가 많이 차이나는 알고리즘을 사용하는 경우에 최악의 상황을 피할 때 사용하기도 하고, 무작위 선택을 여러 번 시도하는 것으로 틀릴 확률을 줄이는 용도로 사용하기도 합니다. 이 글에서는 랜덤을 이용해 여러가지 문제를 통해 문제 풀이에 랜덤을 적용하는 방법을 다룹니다. 목차 랜덤을 이용해 평균 복잡도 보장시키기 퀵정렬 Smallest Enclosing Circle 재밌는 인터랙티브 문제 BOJ18192 보고 정렬 랜덤을 여러 번 시도해 틀릴 확률...
-
Dual
두 번째 주의 AlgoShitPo에서 dual of a planar graph를 작성하게 된 ahgus89입니다. 평면 그래프(planar graph) 평면 그래프란, 이름처럼 평면 위에 놓여져 있는 그래프를 의미합니다. 정확히는, 적당한 평면이 존재하여 어떤 두 간선도 정점을 제외하고 교차하지 않는 그래프를 말합니다. 유명한 평면 그래프와, 그렇지 않은 것들의 예시로는 다음과 같은 것들이 있습니다. $K_5$나 $K_{3, 3}$을 minor로 가지는 것과 평면 그래프가 아님이 동치임이 알려져 있습니다.(Wagner’s theorem) 평면 그래프에서 성립하는 유명한 관계식이 몇 가지 있습니다. 단순 연결 평면 그래프가 $v \geq...
-
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 분석과 큰 연관성을 가지고 있습니다. 어떠한 자료구조의 상태가 있을 때, 그 자료구조가 잘 작동하기 위한 ‘이상적인’ 상태가 존재합니다. 하지만 일반적으로 이 이상적인 상태를 유지하는 것은 그렇게 쉽지 않습니다. 항상 자료구조를 이상적인 상태로 유지하는 것은 굉장히 많은 비용을 요구합니다. 생각해 볼 수 있는 대안은, 자료구조를 매번 갱신하는 것이 아니라 적당히 비효율적인 연산을 하다가, 한...
-
eer tree
https://medium.com/@alessiopiergiacomi/eertree-or-palindromic-tree-82453e75025b 와 Rubinchik, M., & Shur, A. M. (2016). EERTREE: An Efficient Data Structure for Processing Palindromes in Strings. 를 참고하여 작성한 글임을 밝힙니다. Intro ICPC 등의 알고리즘 경진 대회에는 문자열을 다루는 종류의 문제가 자주 출제됩니다. 이런 문자열 문제들을 풀다 보면, 특수한 문자열에 대한 깊은 고찰을 요구하는 상황들이 많이 등장합니다. 이런 특수한 문자열 중 팰린드롬은 오래 전부터 깊은 연구가 진행되어 왔고, 팰린드롬의 성질을 이용하여 관련 문제를 효율적으로 해결하는 다양한 알고리즘이 개발되었습니다. 대표적인 예시로 길이 $...
-
AlgoShitPo 규칙 (2020.02.17)
주제 Pool 글 안 쓰는 사람은 1개 이상의 주제 추가 외부에서도 주제 제안 받음 주제 추가는 깃허브 이슈로 관리 포스팅 주제 선정 주제 pool에서 원하는 주제 선택해서 작성 주제 겹치면 먼저 선점한 사람이 가져감 자신이 제안한 주제는 선택하지 않는 것이 강력히 권장됨 인원 부족시 인원이 모자르면 명시적으로 휴식기 선언 인원 Pool 인원 풀 고정 4명 작성, 나머지 검수 글 작성할 사람 4명 선발 하고 싶은 사람 + 가장 예전에 글 올린 사람 5명 이상 넘어가면 가장 최근에...