-
Minimum Arborescence
안녕하세요. 이번 글에서는 weighted directed graph에서 minimum arborescence를 찾는 알고리즘을 소개해드리려고 합니다. minimum arborescence는 minimum spanning tree의 directed 버전이라고 할 수 있습니다. 문제 가중치 있는 방향 그래프 $G=(V,E)$ 와 루트 정점 $r\in V$이 주어집니다. 가중치는 $e\in E$에 대해 $w(e)$로 정의됩니다. 이때 모든 정점 $u$ 에 대하여 $r\rightarrow u$의 경로가 유일하게 존재하며, 가중치의 합이 최소가 되도록 $|V|-1$개의 간선들을 적절히 선택하는 것이 목표입니다. 편의상 loop와 multi edge는 존재하지 않고, 모든 정점이 $r$ 에서 도달 가능하다고 가정하겠습니다. 해당...
-
How to build WebAssembly app with Rust
서론 작년에 마작에서 현재 들고 있는 패의 점수 기대치를 계산하는 웹 사이트를 제작을 하려고 하고 있었는데, 다음과 같은 문제에 부딪혔습니다. 가능하면 클라이언트 사이드에서 패의 정보를 입력하고, 해당 패의 점수 기대치를 클라이언트에서 계산하게 하고 싶다. 하지만 웹에서 클라이언트 사이드에서 계산하는 선택지는 거의 JavaScript 뿐이다. JavaScript를 사용할 줄은 알지만, 굳이 개발하면서 JS를 쓰고 싶지는 않다. 대안으로 TypeScript가 있지만, 그리고 JS보다 훨씬 낫지만, 역시 마음에 들지는 않는다. 그래서 더 생각해본 결과, 클라이언트 사이드에서 계산하는 것을 포기하고 Python +...
-
De Bruijn 수열
De Bruijn 수열 당신은, 친구에게 $1$에서 $K$까지의 수들을 나열한 원형 수열(끝 글자와 첫 글자가 이어지는 수열)을 선물로 받았다. 그런데 이 수열은 신기한 성질을 가지고 있다. 이 수열에서 길이 $N$인 연속한 부분수열들을 모두 나열한다. 물론 원형 수열이기 때문에 그런 수열의 개수는 수열의 길이와 같다. 이 때, 이렇게 모은 부분수열의 모음이 그러면 $1$에서 $K$까지의 수들로 만든 모든 길이 $N$의 수열의 모음과 같았다! 그런 수열을 de Bruijn(‘jin’이 아니라 ‘ijn’임에 유의하자. 드 브루인이라고 읽는다.) 수열이라 한다. 예를 들어 $K...
-
Android Studio를 이용한 앱 UI 2
Android Studio를 이용한 앱 UI 2 Contents 들어가며 만들 UI 화면 분석 코딩 다른 언어들 발전 방향 들어가며 이전 글에서는 앱 개발에 대한 기본적인 순서와 각 순서별로 간략하게 중요한 것들, 구성되어야 하는 것들에 대해 설명했고, Android Studio tool의 구성에 대해 다루었고, 마지막 부분에 layout에 대한 설명을 간단하게 해주었었습니다. 이번에는 실제 유명한 화면 몇개를 분석하고 직접 코딩하는 부분을 실제로 다루어 보고 UI 제작에 유의미한 여러가지 tool들을 소개하며, 또 이 분야의 발전 방향성에 대해 간단하게 소개하는 것으로...
-
Deep Learning for Symbolic Mathematics
이번 글에서는 ICLR’20에서 spotlight accepted된 논문 Deep Learning for Symbolic Mathematics을 리뷰해보겠습니다. Introduction Symbolic Mathematics (혹은 symbolic computation)는 컴퓨터를 이용하여 기호로 표현된 다양한 수학적 대상들을 다루는 분야입니다. 예를 들어 $x + 1$ 과 $1 + x$ 가 동일한 식이라는 것을 컴퓨터가 자동으로 알아내거나 y에 대한 방정식 $x^2y - 2x + 4 = 0$을 기호 $x$를 이용해 정확하게 푸는 작업을 합니다. 과학 분야에서 주로 사용되는 Scientific Computing은 수치해석(numerical analysis)에 의존하여 approximation을 하지만, Symbolic Mathematics에서는 기호를 이용한...