Samsung Software Membership

junodeveloper

May 19, 2020

STL set을 이용한 Convex Hull Trick 구현

소개 Convex Hull Trick은 여러 일차 함수들의 최댓값이나 최솟값을 찾고자 할 때 유용하게 쓰이는 테크닉입니다. 이미 많은 대회에 출제된 바 있어 최근에는 대회를 준비한다면 필수적으로 알아야 할 테크닉이기도 합니다. 혹시 이 기법에 대해 잘 모른다면 구글 등에 검색하셔서 공부하시는 것을 추천드립니다. 잘 설명된 글들이 많기 때문에 여기서는 기법에 대한 자세한 내용까지는 다루지 않을 것입니다. 주어지는 일차 함수들의 기울기가 증가하거나 감소한다면 스택 자료구조 하나만으로 간단하게 Convex Hull Trick을 구현할 수 있습니다. 만약 그렇지 않고 기울기가 들쑥날쑥한다면...

data-structure geometry

junodeveloper

February 19, 2020

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$ 에서 도달 가능하다고 가정하겠습니다. 해당...

graph-theory

junodeveloper

November 15, 2019

Tree Isomorphism

소개 안녕하세요. 이번 글에서는 Tree Isomorphism에 대해 소개해드리려고 합니다. Isomorphism이란 어떤 두 대상이 수학적으로 동등한 관계에 있음을 나타내는 용어인데, 트리에서의 Isomorphism이라 하면 한쪽 트리의 정점을 적절히 renumbering했을 때 다른 한 쪽 트리와 같아지는 것을 말합니다. (정확히는 그러한 mapping을 가리킵니다.) 이해를 돕기 위해, 다음과 같이 두 개의 트리가 있다고 합시다. 딱 보면 두 트리의 모양이 달라보이지만, 오른쪽 트리의 정점을 아래와 같이 renumbering하면 왼쪽 트리와 완전히 같은 연결 관계를 갖게 됩니다. 즉, 두 트리는 isomorphic합니다. 이처럼 두...

tree graph-theory

junodeveloper

October 20, 2019

Prüfer sequence

소개 안녕하세요. 이번 글에서는 labeled tree를 unique한 수열로 나타내는 Prüfer sequence에 대해 소개해드리려고 합니다. 사실 문제 풀이에 많이 활용되는 개념은 아니지만, 이해하기 쉬우면서도 이를 적용해 풀 수 있는 몇 가지 재밌는(?) 문제가 있어 정리해 보았습니다. Prüfer Sequence Prüfer sequence는 $n$개의 정점을 가진 labeled tree를 다음의 알고리즘에 따라 길이 $n-2$의 수열로 나타낸 것입니다. 트리를 수열로 encode한다는 의미에서 encoding 알고리즘이라고 합니다. function Tree_to_Prüfer(T=(V,E)) a <- an empty array while |V| > 2: u <- leaf node with...

combinatorics algorithm

junodeveloper

September 17, 2019

Half Plane Intersection

소개 안녕하세요. 이번 글에서는 반평면 교집합(Half Plane Intersection)에 대해 소개해드리려고 합니다. 반평면 교집합으로 풀 수 있는 몇 가지 재미있는 문제들이 있는데, 생각보다 관련 자료가 많지 않아서 간단하게나마 정리해 보았습니다. Half Plane Intersection 반평면(Half Plane)이란, 평면 상에 하나의 직선을 그었을 때 나누어지는 각각의 영역을 말합니다. 반평면들이 여러 개 모이면 그 교집합의 형태는 아래와 같이 볼록 다각형(convex hull)이 됩니다. 그럼 대체 이 교집합을 알면 어디에 써먹을 수 있을까요? 후술하겠지만 대표적으로는 볼록 다각형의 내접원을 구하는 데 활용할 수...

geometry algorithm

junodeveloper

July 19, 2019

Network Architecture Search

Intro 기존에는 효율적인 딥러닝 모델을 찾기 위해 수많은 실험을 반복하고 경험적으로 최적의 파라미터를 찾아야 했습니다. 최근에는 이러한 과정을 딥러닝으로 해결하려는 연구가 이루어지고 있는데, 이러한 분야를 AutoML이라고 합니다. 즉, 딥러닝으로 딥러닝 모델을 찾는 것이라 할 수 있습니다. 이 글에서는 대표적인 AutoML 방법인 NAS(Network Architecture Search)와 NASNet에 대해 소개하려고 합니다. NAS 먼저 소개할 논문은 2017년 ICLR에 발표된 논문 “Neural Architecture Search with Reinforcement Learning”입니다. NAS라고 알려진 이 논문은 강화학습을 이용한 뉴럴네트워크 구조 탐색 방법에 대해 소개하는데, 아래에서...

deep-learning