-
빠른 격자점 세기
서론 우리는 어떤 그래프 내부의 격자점을 세어야 할 일이 있는 경우가 있다. 예를 들면, 원 안의 격자점의 갯수를 세는 것은 $\pi$ 의 값과 피타고라스 쌍과 관련이 있으며, 약수의 갯수의 합을 구하려 $f(x) = \frac{N}{x}$ 내부의 격자점의 수를 세기도 한다. 여기서는 이 전략을 구체화 시켜서 convex hull 위의 점의 갯수로 문제를 푸는 방법에 대해 알아보고, 또한 약수의 갯수를 $\tilde{O}(n^{\frac{1}{3}})$ 에 세는 방법을 알아본다. 약수 두 자연수 $A$, $B$에 대해서 $B$로 $A$를 나눴을 때 나누어 떨어지면, 우리는...
-
Treap
목차 1. 개요 2. 개념 3. 구현 4. 응용 5. 문제풀이 6. 마무리 7. 참고자료 개요 이 포스트를 쓰며 언제 한번, Treap의 활용성에 대해서 적고 싶었다. 물론 여기서 내가 여러분에게 소개하고자 하는 것은 Treap을 BST로서 다루는 것이 아닌, 배열을 자유롭게 붙이고 떼고 뒤집는 것에 설명하기 위함이다. Treap은 기본적으로 BST로서 사용할 수 있지만, Splay Tree 처럼 배열을 다루는 데 사용할 수 있다. Splay Tree 처럼 여러가지의 method 들을 활용하여 amortized 시간을 내는것은 아니고, 확률에 의존하는 경향이...
-
Listen, Attend and Spell
소개 전통적으로 음성 인식 모델은 음향 모델(acoustic model), 발음 모델(pronounciation model), 언어 모델(language model) 등 다양한 구성 요소로 이루어져 있었고 각각의 모델을 따로 학습하여 사용했습니다. 음성 인식 분야에서 Listen, Attend and Spell (ICASSP 2016)은 end-to-end 방식으로 학습할 수 있는 뉴럴넷 모델을 제시합니다. Sequence to sequence with attention Listen, Attend and Spell(LAS)는 sequence to sequence framework와 attention 기법을 사용하여 음성 인식을 합니다. sequence to sequence(seq2seq) 모델은 가변길이의 입출력 시퀀스를 학습할 수 있도록 설계되었습니다. seq2seq 모델은 encoder...
-
프로그래밍 대회를 개최하기 위한 10가지
프로그래밍 대회를 개최하기 위한 10가지 이 글은 Ajou Programming Contest(2016-19 APC), 경인지역 6개대학 연합 프로그래밍 경시대회(2016-19 shake!), 전국 대학생 프로그래밍 대회 동아리 연합 여름 대회(2016 UCPC)를 운영했던 제 경험을 토대로 작성되었습니다. 프로그래밍 대회를 개최하려는 분들께 조금이나마 도움이 되었으면 하는 마음으로 대회를 맡으며 경험했던 시행착오를 모아 필요한 10가지를 정리해보았습니다. 어디까지나 제 개인의 경험에 기반한 내용으로 대회를 열기 위해서는 이래야 한다!가 아닌 아래 과정을 고려해보자는 의미로 읽어주시면 좋겠습니다. 일의 진행 순서로 나열하긴 했지만 모든 과정은 유기적입니다. 대회의...
-
PageRank
PageRank 페이지랭크(PageRank)는 구글의 설립자로 널리 알려진 래리 페이지와 세르게이 브린이 개발한 알고리즘으로, 웹 문서의 중요도를 구할 때 사용합니다. 이 포스트에서는 페이지랭크 알고리즘의 원리와 어떻게 작동하는지에 대해 다룹니다. 웹을 그래프 형태로 나타내기 PageRank 알고리즘에서는 월드 와이드 웹의 문서들을 노드로 대응시키고 문서에서 다른 문서로 넘어가는 하이퍼링크를 간선으로 대응시켜서, 유방향 그래프로 웹을 나타냅니다. 보통 이러한 그래프를 웹 그래프라고 합니다. 예를 들어, 이 글과 이 글이 레퍼런스한 문서들이 그래프의 노드에 해당하고, Reference로 넘어가는 하이퍼링크가 방향이 있는 그래프에서 간선에 해당합니다....