-
Geometric spanning tree
Geometric Spanning Tree $d$ 차원 좌표공간 상에 크기 $N$ 의 점 집합 $S$ 가 주어졌을 때, 집합 $S$ 를 정점 집합으로 하며 각 정점 쌍마다 두 점의 거리를 가중치로 한 그래프를 생각할 수 있다. 이러한 그래프에서 최소 스패닝 트리를 찾는 문제를 Minimum Geometric Spanning Tree 라고 한다 (Encyclopedia of Algorithms 533p). 두 정점의 “거리” 를 지정하는 방법은 여러 가지가 존재하고, 이 거리계를 어떻게 지정하느냐에 따라서 문제를 해결하는 양상이 많이 달라진다. 일반적으로 사용하는 거리계는 $L_1$ metric...
-
Android Studio를 이용한 앱 UI
Android Studio를 이용한 앱 UI Contents 앱 공부를 시작하며 앱 개발의 구성 Android Studio 구조 레이아웃 마치며 Reference 앱 공부를 시작하며 앱 공부를 시작하게 된 계기는 백지상태로 참여한 학교에서 주최한 해커톤 대회 때문이었다. 예전에 잠깐 만져본 것 이외에는 아예 처음 접해보는 분야여서 많은 어려움도 있었지만 나름의 매력이 있고 재미있는 분야라는 생각이 들었다. 따라서 대회가 끝나고 난 후에도 조금 더 공부를 해보았고 처음 도전해보는 사람들도 쉽게 접할 수 있고 이해할 수 있는 분야라는 생각이 들어서 글을...
-
Pay Less Attention with Lightweight and Dynamic Convolutions 리뷰
컨볼루션 그림은 이 글(https://qiita.com/koreyou/items/328fa92a1d3a7e680376)을 참고해서 만들었습니다. 소개 시퀀스-투-시퀀스(Sequence-to-sequence) 모델은 자연언어처리(Natural Language Processing) 분야의 다양한 테스크를 처리하기 위해 쓰이고 있습니다. 이중 수많은 SOTA 모델이 “Attention Is All You Need”에서 소개된 트랜스포머(Transformer)를 기반으로 설계되어있고 이 모델에서 사용하는 어텐션 기법인 셀프 어텐션(self attention)은 SOTA 성능을 달성하기 위해 꼭 필요한 구조로 여겨지곤 합니다. WMT2014 영어-독일어 데이터 셋에서 기계 번역 모델의 성능 순위 (2019.12.30) “Pay Less Attention with Lightweight and Dynamic Convolutions”은 facebook AI research 팀의 논문으로 ICLR 2019에서 공개되었습니다....
-
Mo's Algorithm on Trees
이 게시글은 LCA(lowest common ancestor)에 대한 지식이 선행되어야 하지만 본 글에서는 소개하지 않습니다. Mo’s Algorithm이란? Mo’s algorithm은 평방 분할(sqrt decomposition)의 일종의 활용 기법으로, 오프라인으로 구간 쿼리 문제를 해결할 때 사용할 수 있습니다. 이미 이에 관한 좋은 글이 있어 (링크)로 대체하겠습니다. Mo’s Algorithm on Trees? 위 Mo’s Algorithm을 Tree에서 하는 것을 의미합니다. Mo’s는 앞서 말씀드렸던 것처럼 구간 쿼리 문제를 해결할 때 쓰이기 때문에 트리에서의 쿼리를 구간 쿼리처럼 나타낼 필요가 있는데요. 이를 Euler Tour on Trees를 이용하여...
-
최대 이분 매칭에 관한 몇 가지 정리
이분 그래프(Bipartite Graph)에서의 최대 매칭(Maximum Matching)은 최대 유량(Maximum Flow)과 같습니다. 이 글에서는 위와 같이 최대 유량과 최대 이분 매칭에 관한 기본적인 문제를 해결 할 수 있는 분들을 위해 최대 이분 매칭에 관한 대표적인 정리를 예제와 함께 다룹니다. 구성은 아래와 같습니다. Minimum Vertex Cover - BOJ 1867 돌멩이 제거 Maximum Independent Set - BOJ 11014 컨닝 2 Minimum Path Cover - BOJ 1671 상어의 저녁식사 Maximum Anti-Chain - BOJ 13441 마법의 나무 Minimum Vertex Cover Vertex...