-
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} )$ 위와 같은 점화식으로 간단히 해결할 수...
-
트리의 종류와 이해
트리의 종류와 이해 0. 목차 목차 tree란? tree의 종류 결론 참고자료 1. tree란? tree 자료구조는 그래프의 한 종류로, 정의 내리자면 트리란 어떤 노드들의 집합으로 노드들은 각 서로 다른 자식을 가지며 이 때 각 노드는 재사용 되지 않는 구조이다. tree 에는 여러가지 특징들이 존재한다. tree 의 서로 다른 임의의 두 노드에 대해 두 노드를 연결하는 경로는 유일하다. tree 에는 사이클을 가지는 노드 집합이 존재하지 않는다. tree 반드시 하나의 root가 존재한다. (부모 노드가 존재하지 않는 노드) 이런...
-
알고리즘 문제 풀이2
알고리즘 문제 풀이 4월에 푼 재미있는 문제들의 풀이를 작성해보았습니다. 문자열 장식 N개의 문자열이 주어지면 이 문자열들을 합쳐서 만들수 있는 사전순으로 가장 앞서는 문자열을 구하는 문제입니다. 단, 각 문자열 안에서의 상대적인 순서는 유지해야합니다. 우선 상대적인 순서를 유지해야 하니까 주어진 문자열들의 앞글자부터 하나씩 때어 온다고 생각합시다. 그러면, 매순간 각 문자열의 앞글자들 중에 사전순으로 가장 작은 알파벳이 있다면 그것을 때어 오는 것이 이득이라는 것을 쉽게 알 수 있습니다. 그런데 이러한 문자열이 여러개가 있으면 어떤 문자열에서 때어오는 것이 이득일까요?...