-
이산 로그(Dicrete Logarithm)
이산 로그란? 수학에서의 로그는 모두 익숙할 것입니다. $a^x = b$일 때 $x = log_a b$입니다. 실수에서는 $a, b$가 주어졌을 때 $a^x = b$를 만족하는 $x$, 즉 $log_a b$를 아주 간단하게 계산할 수 있습니다. 그러나 $Z_p$에서는 이를 계산하는 것이 간단하지 않습니다. 이와 같이 $Z_p$에서 주어진 $a, b$에 대해 $a^x = b$를 만족하는 $x$를 찾는 문제가 바로 이산 로그(Discrete Logarithm) 문제입니다. 이산 로그 문제에서 $p$는 소수, $a$는 $p$의 원시근인 것이 좋습니다. $a$가 $p$의 원시근이라면 $a^0, a^1, a^2,...
-
그룹 road to grandmaster 둘러보기
어느 ELO 레이팅이 안 그러겠냐만은, grandmaster라는 칭호는 세계적인 실력자에게 주어지는 칭호입니다. 가장 유명하고 세계적인 Competitive Programming(CP) 플랫폼인 Codeforces에서는 레이팅 2400 이상일 경우 grandmaster로 인정받으며, 닉네임이 붉은 색으로 변합니다. 한국 PS계에서는 이들을 ‘레드’라고 부르기도 합니다. 레드가 어느 정도 수치인지 대략적으로 가늠하자면, 2019년 5월 7일 기준으로 최근 6개월간 rated 대회를 친 사람 중 전 세계에 352명밖에 없습니다 (한국에선 16명). 국내 수준급의 프로그래밍 경시 대회의 대략적인 최소 입상 수준이 레이팅 1900-2100 (통칭 ‘퍼플’)이라는 점을 고려하면 단순히 닉네임에서 빛나는...
-
Audio rendering in web
HTML Video 태그를 대신 할 비디오 플레이어를 웹 기술을 통해 만든다고 상상해보세요. 영상을 재생하기 위해서는 두 가지가 필요하죠. 비디오 렌더링과 오디오 렌더링입니다. 비디오 렌더링을 위해서는 HTML Canvas API를 사용하면 될 것 같고, 오디오 렌더링을 위해서는 Web Audio API를 사용하면 될 것 같습니다. (영상 디코딩은 이미 끝났다고 가정하죠. 편의상 이미 디코딩된 영상 데이터를 서버로부터 스트리밍 받고 있다고 생각합시다. 현재의 네트워크 기술로는 허무맹랑한 이야기지만요.) 이전 포스트에서 Offscreen Canvas라는 API를 언급한 적이 있습니다. 웹 상에서 무거운 그래픽 렌더링...
-
Introduction to matroid
Matroid 정의 1. matroid $\mathcal{M} = (S, \mathcal{I})$ 에서 $S$는 유한집합, $\mathcal{I} \subset 2^S$ 는 독립집합(independent set)들의 collection이다. 이 때, $I$는 다음 세 가지 조건을 만족하여야 한다. $\phi \in \mathcal{I}$ $Y \subset X, X \in \mathcal{I} \Rightarrow Y \in \mathcal{I}$ $X, Y \in \mathcal{I}, \lvert X \rvert < \lvert Y \rvert$ 이면 $X + y \in \mathcal{I}$ 를 만족하는 $y \in Y \setminus X$가 존재 매트로이드는 다양한 집합에서 정의될 수 있다. 그 중 대표적인 예...
-
Atcoder Educational DP contest 풀이
Atcoder에서 열렸던 Educational DP contest 문제들에 대한 풀이입니다. 자주 나오는 다이나믹 프로그래밍 유형들을 연습할 수 있는 좋은 셋이라고 생각합니다. 문제마다 간략한 풀이를 작성했습니다. 코드는 Atcoder에서 자유롭게 열람이 가능하므로 문제마다 링크를 달아두었습니다. 어느정도는 난이도 순서대로 정렬되어 있지만, 사람마다 느끼는 난이도가 다를 수 있습니다. A. Frog 1 문제 링크 $d_i :$ $i$ 번째 Stone까지 도달하는 최소 비용 $d_i = min(d_{i-1} + h_i - h_{i-1} ,\ d_{i-2} + h_i - h_{i-2} )$ 위와 같은 점화식으로 간단히 해결할 수...