-
Generalized Sorting with Predictions
이 글에서는 Pinyan Lu 외 3인의 논문 “Generalized Sorting with Predictions”에 대해 소개합니다. (글이 발행된 이후에 koosaga님의 project_tcs에 영상 및 자료가 올라갈 예정입니다.) 1. Generalized Sorting Problem 1.1. 문제의 정의 어떤 object들을 정렬하는 것은 컴퓨터 과학에 있어 매우 중요한 문제입니다. 일반적으로 우리가 (comparison-based) 정렬을 한다고 할 때, 우리는 임의의 원소 간의 “비교”가 가능한 상황을 상정합니다. Generalized sorting problem에서는 이 상황을 보다 일반화하여 일부 원소들 사이에는 비교 연산을 이용할 수 없는, 즉 일부 원소들 간의 비교만...
-
오일러 회로와 경로
이 글에서는 연결 무방향 단순 그래프를 다룹니다. 오일러 회로 그래프의 모든 간선을 단 한 번씩 지나서 시작점으로 돌아오는 경로를 오일러 회로라고 합니다. 연결 그래프면서 차수가 홀수인 정점이 없다면 오일러 회로가 존재합니다. 그리고 오일러 회로가 존재한다면 차수가 홀수인 정점이 없습니다. 오일러 회로와 관련된 문제를 풀기 위해서는 이 필요충분조건만 알고 있어도 되지만 아래에 서술할 증명이 간단하기에 한 번쯤 읽고 넘어가는 것을 추천합니다. 그래프에서 사이클이 존재하지 않기 위해선 트리가 되어야 하지만 트리에는 차수가 홀수(1개)인 리프 노드가 존재하기 때문에...
-
접미사 트리 (파트 2: Ukkonen의 알고리즘)
이전 글에서 이어집니다. Ukkonen의 $O(m^3)$ 알고리즘 Ukkonen의 알고리즘은 접미사 트리를 $O(m)$에 만드는 알고리즘입니다. 하지만 이를 모두 설명하기에는 너무 복잡하니, 비효율적인 버전을 먼저 서술하고 시간 복잡도를 점차 줄여 나갑시다. (구현할 때도 파트 1을 먼저 구현하고, stress test 등으로 구현이 정확함을 확인하시는 것을 권합니다.) $S[1..i]$의 접미사 트리를 $I_i$라고 표기합시다. Ukkonen의 알고리즘의 큰 그림은 $I_1$에서 시작해서 이것을 $I_2$로 확장하고, $I_3$, $\cdots$, 마지막으로 $I_m$으로 확장하는 것입니다. $m$번째 글자가 끝 문자라고 가정하면 $I_m$의 모든 리프 노드와 접미사가 일대일 대응이 되지만,...
-
Generator 문제 풀이 / 후기 (스포일러 주의)
개요 Generator 문제는 수많은 PS 문제들 중에서도 오로지 ‘구현’만으로 악랄한 난이도를 성립시킨 것으로 유명합니다. solved.ac 기준 Diamond III라는 상당한 고난도의 평가를 받고 있지만 이 문제를 풀기 위한 사전 지식이나 개별 테크닉은 높아야 Platinum 중상위권으로 생각하며, 문제의 난이도는 대부분 구현, 관찰, 그리고 요구하는 끈기와 인내심에 의해 결정된다는 점에서 다른 구현 위주의 고난도 문제들과는 차별이 되는 문제입니다.1 최근 문제 풀이를 연습할 시간이 부족했던 저에게 갑자기 이 문제를 당일치기로 풀어내는 것은 상당히 어려운 일이었고, 비록 주말이긴 했으나 거의...
-
Expander Decomposition and Pruning: Faster, Stronger, and Simpler
Expander Decomposition and Pruning: Faster, Stronger, and Simpler 알고리즘에서 분할 정복 은 큰 문제를 부분 문제로 나누는 과정을 뜻한다. 이 때 부분 문제들이 가져야 하는 특징은, 원래 문제보다 쉬워야 하고, 부분 문제를 합칠 수 있어야 한다. 예를 들어서, Heavy Light Decomposition은 트리에서 큰 문제를 부분 문제로 나누는 과정에서 자주 등장한다. 각 문제가 쉽고 (직선), 합치는 것이 가능 (Light edge를 통해서 묶음) 하기 때문이다. 트리의 경우에는 HLD 외에도 다양한 분할 정복 기법이 존재하지만, 그래프를 분할 정복하는...