-
키보드 음성 키로거
1. Introduction 최근에 참가한 PBCTF 2021에서 Ghost Writers라는 이름의 문제를 보다가 굉장히 흥미로운 주제를 알게 되어 소개해드립니다. 특히 음성 인식과 머신 러닝에 관심이 많은 분이라면 좋은 연구 주제가 될 수 있다고 생각합니다. 트위치나 아프리카와 같은 플랫폼에서 여러 스트리머의 방송을 보다보면 마이크를 꺼두지 않는 한 방송 중에 기계식 키보드의 타이핑 소리가 그대로 송출이 되는 경우가 거의 대다수입니다. 이 타이핑 소리로부터 무언가 의미있는 정보를 얻기는 어려울 것 같지만, 혹시 지금 주변에 기계식 키보드가 있다면 여러 키를 눌러보았을...
-
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...