-
Constructing a Distance Sensitivity Oracle in $O(n^{2.5794}M)$ Time
Constructing a Distance Sensitivity Oracle in $O(n^{2.5794}M)$ Time 가중치 있는 방향 그래프 $G$ 에서 두 정점 $s, t$ 가 쿼리로 주어질 때, $s$ 에서 $t$ 로 가는 최단 경로를 구하는 문제를 흔히 모든 쌍 최단 경로 문제 (All-Pair Shortest Path, APSP) 문제라고 부른다. APSP 문제는 그래프 이론의 기초적인 문제 중 하나로, Floyd-Warshall Algorithm을 사용하여 $O(n^3)$ 시간에 해결하는 방법이 아주 잘 알려져 있으며 알고리즘을 공부하다 보면 누구나 접하게 될 기초 알고리즘 중 하나이다. Floyd Warshall Algorithm은...
-
트리 압축
개요 트리에 관한 문제를 풀다 보면, 일부 정점만이 쿼리로 들어왔는데 모든 정점을 검사하기에는 비효율적인 경우가 있습니다. 이 때 필요 없는 정점과 간선들을 지워서 새로운 트리를 만드는 기법을 트리 압축이라고 부릅니다. 다른 말로는 Virtual Tree / Auxiliary Tree라고도 합니다. 다음 예시를 통해 트리 압축이 정확히 무엇인지와 어떻게 구현하는지에 대해서 살펴보겠습니다. JOI Open Contest 2014. 공장들 정점이 $N$개인 간선 가중치 트리와 $Q$개의 쿼리가 주어집니다. $i$번 쿼리마다 서로소인 두 정점 부분집합 $S_i$와 $T_i$가 주어지면, $S_i$의 한 정점에서 $T_i$의...
-
영 타블로의 조합론적 의미와 알고리즘적 응용 (1)
개요 영 타블로(Young tableaux)는 20세기 초반, 알프레드 영(Alfred Young)이 제안한 객체로, 조합론에서 군(Group)을 표현할 때 유용하게 사용할 수 있는 특수한 형태의 행렬이다. 본 글은 다소 어려운 개념인 영 타블로를 쉽게 서술하고, 조합론적인 의미를 설명하며, 이를 활용하여 얻을 수 있는 효율적인 알고리즘과 새로운 문제 해결 관점 등을 소개하고자 한다. 본문은 특별한 배경지식을 가지지 않아도 읽고 이해할 수 있도록 작성되었다. 용어의 정의 영 다이어그램 영 타블로에 대하여 이야기하기 전에, 먼저 영 다이어그램(Young diagram)을 정의하자....
-
Minimum $s - t$ cut of a planar undirected graph in $O(n \log^2 n)$ time
Minimum $s - t$ cut of a planar undirected graph in $O(n \log^2 n)$ time 간선에 가중치가 있는 그래프가 주어졌을 때, 최소 $s - t$ 컷은 두 정점 $s, t$ 가 연결되지 않게 하기 위해 지워야 하는 간선 집합의 최소 가중치 합을 뜻한다. Min-cut Max-flow theorem에 의해서, 최소 $s - t$ 컷은 최대 유량 알고리즘을 사용하여 다항 시간에 구할 수 있음이 잘 알려져 있다. 그래프의 최소 컷과 최대 유량의 중요성에 대해서는 이미 여러 번의 SW...
-
WYSINWYX: What You See Is Not What You eXecute
1. Introduction 글을 시작하기에 앞서, 이 글에서 다루는 논문 WYSINWYX: What You See Is Not What You eXecute 는 카이스트 차상길 교수님의 IS-561: Binary Code Analysis and Secure Software Systems 과목에서 읽어보면 좋은 논문으로 소개된 논문입니다. 과목 링크에 들어가보시면 이외에도 정보 보안의 근간을 이해하는데에 있어서 도움이 될 여러 논문들을 소개하고 있으니 확인해보시는 것을 추천드립니다. WISINWYX는 WISIWYG이라는 표현으로부터 따온 재치있는 표현입니다. 저는 WISIWYG를 아주 먼 옛날 워드프로세서 필기를 공부하며 들어본 것 같은데, WISIWYG는 What You See...