-
Variation of Mo's Algorithm 2
안녕하세요 jthis 입니다. 이 글에서는 Variation of Mo’s Algorithm 1에 이어 또다른 Mo’s Algorithm의 variation에 대해 소개하겠습니다. Mo’s Algorithm with Update Mo’s Algorithm은 쿼리 문제를 효율적으로 해결하는 알고리즘입니다. 하지만 일반적인 Mo’s Algorithm은 업데이트 연산을 처리할 수 없어, 해당 제약으로 인해 사용하기 어려운 경우가 있습니다. 이런 상황에서 사용할 수 있는 3D Mo’s Algorithm이라고도 불리는 Update Mo’s Algorithm에 대해 소개하고자 합니다. 예를 들어, 쿼리문제를 생각해 봅시다. 이 문제에서는 다음과 같은 연산이 주어집니다: 1 i x: $A_i$를 x로...
-
그래프 채색 개론
서론 (무향) 그래프 $G$는 정점 집합 $V$와 간선 집합 $E$ 로 이루어진 구조입니다. 간선은 두 원소를 잇는 (순서가 없는) 선입니다. 여기서 그래프의 정점을 색칠한 다는 것은, 간선의 양 끝이 다른 색이 되도록 색칠한다는 것입니다이 게시글에서는 그래프 색칠에 대한 다양한 주제를 다룹니다. 해당 주제는 그래프 색칠에 대한 시각을 늘려줄 것이라고 생각합니다. 다룰 주제는 다음과 같습니다. 주제 이분그래프 색칠 그리디 색칠, $(\Delta+1)$색 정리, $6$색 정리 $5$색 정리, $4$색 정리, Kempe Chain, $\Delta$색 정리 채색 다항식 표기법 이...
-
Rust의 GC를 직접 구현해보자
서론 Rust는 GC가 없는 언어입니다. 하지만 지난 글에서 살펴보았듯이 Rust에서도 GC가 필요한 경우가 있습니다. 그래서 이번 글에서는 Rust에서 GC를 직접 구현해보려고 합니다. GC 구조 설계 Rust는 ownership 시스템으로 인해 GC를 구현하는 것이 까다롭습니다. C/C++ 등의 언어에서는 단순히 포인터를 사용하면 되지만 Rust에서는 포인터를 사용할 때마다 ownership을 고려해야 합니다. 물론 unsafe를 사용하면 ownership을 고려하지 않고도 포인터를 사용할 수 있지만, 이번 글에서는 unsafe를 최대한 사용하지 않고 GC를 구현해보려고 합니다. Rust에서 GC를 구현하기 위해서는 다음과 같은 구조가 필요합니다. 그럼...
-
Massively Parallel Computation
이 글에서는 parallelism과 관련하여 최근에 제시된 두 계산 모델에 대해 간단히 알아본다. 또한, 그 계산 모델 상에서 돌아가는 잘 알려진 (그러면서도 이론적으로 중요한) 문제에 대한 알고리즘 및 계산 이론적 결과를 알아본다. 다만 이 주제에 대해 deep 하고 formal한 내용은 전혀 다루지 않는다. 전반적으로 두 계산 모델에 대한 이해를 조금 만드는 정도를 목표로 한다. 이 글에서 “높은 확률”은 최소한 1 - (polynomially small) 이상이라 이해하면 좋다. Massively Parallel Computing Model (MPC) 먼저, Massively Parallel Computing Model(MPC)에...
-
The Cut-Matching Game: Expanders via Max Flow
알고리즘에서 분할 정복 은 큰 문제를 부분 문제로 나누는 과정을 뜻한다. 이 때 부분 문제들이 가져야 하는 특징은, 원래 문제보다 쉬워야 하고, 부분 문제를 합칠 수 있어야 한다. 알고리즘 연구에서 분할 정복이 가지는 중요성은 어마어마하지만, 그래프에 대한 분할 정복에 대해서는 좋은 결과를 얻지 못했다. 오랜 시간 동안 이러한 분할 정복 은 트리, 평면 그래프, 혹은 이와 유사한 그래프에서만 가능한 것으로 알려져 있었다. 하지만, 그래프 알고리즘과 최적화 이론의 결합이 여러 의미 있는 성과들을 내면서, 이러한 분할...