-
Poly-logarithmic Randomized Bellman-Ford (1/2)
Introduction Single-Source Shortest Path (SSSP) 문제는 알고리즘 입문에서부터 다루는 아주 기초적이고, 또 중요한 문제입니다. 엄밀하게 적자면, $n$개의 정점과 $m$개의 가중치 있는 단방향 간선을 갖는 그래프 $G$와 시작 정점 $s$가 주어질 때, 모든 점 $i$에 대해 $s$에서 $i$로 가는 최단 경로의 길이 $\mathrm{dist}(s, i)$ 를 묻는 문제입니다. 일반적으로 가중치가 모두 양수인 경우에 사용할 수 있는 Dijkstra’s algorithm과 가중치의 값과 무관하게 사용할 수 있는 Bellman-Ford algorithm이 가장 유명합니다. 각각의 시간 복잡도는 $\mathcal{T}[\text{Dijkstra}]$: Practical한 선에서 $O(m \log n).$...
-
구간 최장 증가 부분 수열 쿼리 (Part 2)
Chapter 4. $\boxdot$ 연산자의 빠른 구현 현재 우리의 알고리즘이 $O(N^5)$ 인 이유는 다음과 같다: $\boxdot$ 연산자가 $O(N^3)$ 에 구현됨 $\boxdot$ 연산자를 $O(N^2)$ 번 호출함 잠시 $\boxdot$ 연산자의 실제 이름을 짚고 넘어가자면, 논문에서는 위 연산자가 unit-Monge matrix-matrix distance multiplication 라는 이름으로 소개되었다. Part 1에서는 괜히 글이 어렵다는 인상을 줄 것 같아서 의도적으로 언급하지 않은 이름이다. 이제부터는 (순열의) unit-Monge 곱 이라고 부르거나 그냥 앞과 같이 $\boxdot$ 이라고 부른다. $\boxdot$ 연산자를 어떻게 $O(N \log N)$ 에 계산하는지 살펴보자....
-
Introduction to Hardness Proofs and 3SUM Conjecture
Introduction to Hardness Proofs and 3SUM Conjecture Introduction 어떤 문제를 푸는 가능한 한 빠른 알고리즘을 찾아내는 것은 이론전산학 분야의 주된 관심사 중 하나입니다. 어떠한 문제든 우리가 원하는 만큼 빠른 알고리즘이 존재한다면 좋겠지만, 아쉽게도 이는 사실이 아닙니다. 예를 들어, $N$개의 정수를 크기 순으로 정렬하는 데에는 적어도 $\mathcal{O}(N\log N)$ 시간이 필요하다는 사실이 알려져 있습니다. 그렇다면 질문을 바꿔서, 어떤 문제를 해결하는 알고리즘의 시간 복잡도의 하한을 알 수는 있을까요? 이를 다른 말로 해당 문제의 hardness을 알아낸다고 말하는데, 이 역시도...
-
Noise or Signal: The Role of Image Backgrounds in Object Recognition (ICLR 2021)
Noise or Signal: The Role of Image Backgrounds in Object Recognition (ICLR 2021) Deep learning 분야에서, 모델의 generalization을 올리는 것은 굉장히 중요한 일입니다. Generalization이 떨어지는 모델의 경우, 주어진 학습 데이터에만 과적합하여 이외의 다른 데이터들에 대해서는 성능이 낮아지는 문제가 발생할 수 있으며, 주어진 train data들만이 가지는 특성들에 대해 큰 bias를 가지게 될 수 있습니다. 이러한 문제를 해결하기 위한 방법론들은 굉장히 다양한 접근들로 제시되어왔습니다. Train data를 건드리는 data augmentation들도 존재하고, train 과정에서 과적합되는 것을 방지하기 위한 sharpness-aware,...
-
Quantum Graph
서론 그래프는 수학과 컴퓨터 과학에서 굉장히 중요하게 다루는 내용이다. 알고리즘 문제풀이만 하더라도 그래프와 관련된 알고리즘이 수 없이 많다. 이러한 그래프 이론은 최단 경로, 효율적인 네트워크 구조, 데이터 분석 등에 폭넓게 응용된다. 다들 기존에 자주 보던 그래프 (고전 그래프)에 대해서는 어느정도 익숙할 것이라 생각한다. 양자 컴퓨팅 분야가 발전하면서 고전 컴퓨팅에 존재하던 다양한 개념들을 양자 컴퓨팅으로 옮겨오는 연구들도 많이 진행되었다. 이는 한 학문이 발전하면서 흔히 보이는 현상이다. 본 글에서는 Graph의 개념을 옮겨온 Quantum Graph에 대해 소개해 보고자...