-
클러스터링(군집화) 개요
클러스터링(군집화) 클러스터링(군집화)은 개체들이 주어졌을 때, 개체들을 몇 개의 클러스터(부분 그룹)으로 나누는 과정을 의미합니다. 이렇게 개체들을 그룹으로 나누는 과정을 통해서, 클러스터 내부 멤버들 사이는 서로 가깝거나 비슷하게, 서로 다른 두 클러스터 사이의 멤버 간에는 서로 멀거나 비슷하지 않게 하는 것이 클러스터링의 목표입니다. 만약에 개체들을 거리 공간 안에 나타낼 수 있다면, 개체와 개체 사이에 거리(metric)를 정의할 수 있습니다. 예를 들어 개체들을 유클리드 공간 안에 나타낼 수 있다면, 유클리드 거리를 정의할 수 있습니다. 이러한 경우에 클러스터링의 목표는 같은...
-
이산 로그(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$가 존재 매트로이드는 다양한 집합에서 정의될 수 있다. 그 중 대표적인 예...