-
Faster Matroid Intersection - Part 1
0. Introduction 필자는 Matroid를 소개하는 글 및 Matroid Intersection을 소개하는 글을 2019년에 작성한 바 있다. Matroid Intersection은 해당 글에도 나와 있듯 다양한 문제들을 해결할 수 있는 툴이 되며, 이에 따라 많은 연구가 진행되었다. 특히, 2019년을 기점으로 하여 Matroid Intersection을 어떻게 하면 빠르게 할 수 있을지에 대해 여러 논문의 결과가 발표되기 시작했다. 대표적인 예시로 다음과 같은 4가지 논문이 존재하고, 앞으로는 다음 논문들의 결과에 대해 다룰 것이다. A note on Cunningham’s algorithm for matroid intersection(2019) Faster Matroid...
-
Choice Coordination Problem
개요 문제 상황 $n$개의 프로세서가 존재한다. 각 프로세서는 $m$개의 선택지 중 하나를 선택해야 한다. 그런데, 프로세서들이 완전히 비동기적으로 작동한다. 프로세서가 공유하는 일관적인 시계 (global clock)이 존재하지도 않을 뿐더러, 프로세서의 응답 속도에 대한 가정을 할 수도 없다. 이러한 상황에서 모든 프로세서가 동일한 선택으로 합의하도록 하는 알고리즘이 필요하다. 인격을 부여해 이러한 비유 상황을 만들어낼 수 있다: $n$명의 관광객이 존재한다. 그들이 머무는 여행지는 $m$개의 방으로 이루어져 있다. 이 때 관광객 모두가 방 하나에 모일 수 있도록 행동 규약을...
-
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를 구현하기 위해서는 다음과 같은 구조가 필요합니다. 그럼...