-
그래프의 간선 색칠 문제
그래프의 간선 색칠 문제 그래프 $G$가 주어질 때, 각 정점 $v$에 대해 자연수 색상 을 배정하여 간선으로 직접 연결된 정점 쌍마다 다른 색상을 배정해야 한다. 이 때, 배정된 최대 색상을 최소화해보자. 즉, 서로 다른 색의 수를 최소화해야 한다. 이 문제는 그래프의 정점 색칠 (Graph Coloring, Vertex Coloring) 문제로, NP-complete임이 잘 알려져 있다. 너무 어려우니까 다른 문제를 생각해 보자. 그래프 $G$가 주어질 때, 각 간선 $v$에 대해 자연수 색상 을 배정하여 간선으로 직접 연결된 정점 쌍마다...
-
동적 계획법을 최적화하는 9가지 방법 (Chapter 4)
동적 계획법을 최적화하는 9가지 방법 (Chapter 4) 이 글은 Chapter 3에서 계속된다. 9. Dynamic Tree DP Dynamic Tree DP는 특수한 형태의 Tree DP를 최적화할 수 있는 방법으로, 일반적인 직선에서 행렬과 같은 구조를 사용하여 DP를 최적화하는 것과 비슷한 방식이다. 사실 Tree DP가 아니라 일직선에서 하는 DP 문제라 하더라도 최적화 방법이 자명하지 않기 때문에, 이 글에서는 먼저 일직선에서의 DP 최적화를 먼저 설명한다. (일직선에서의 이러한 DP 최적화를 부르는 말은 잘 모른다.) In Line 다음과 같은 문제를 생각해 보자....
-
동적 계획법을 최적화하는 9가지 방법 (Chapter 3)
동적 계획법을 최적화하는 9가지 방법 (Chapter 3) 이 글은 Chapter 2에서 계속된다. 8. Circular LCS 두 문자열 $S, T$ 가 주어질 때 둘의 LCS를 구하는 문제는 잘 알려져 있고, $n = S, m = T$ 일 때 $O(nm)$ 보다 빨리 하기 힘든 것으로도 유명하다. Circular LCS 문제는 $S$ 를 Cyclic shift 할 수 있을 때, 각 cyclic shift에 대해서 LCS를 계산하는 문제이다. 기호로 표현하면, 모든 $0 \le i \le S - 1$ 에 대해, $LCS(S[i:]...
-
Cactus graph realization of degree sequence
Degree sequence 그래프에서, Degree sequence란 undirected graph의 각 정점의 차수(degree)를 늘어놓은 수열을 말한다. Graph realization problem이란, 수열이 주어졌을 때 그 수열을 degree sequence로 갖는 그래프를 실제로 construct하는 문제를 말한다. 여기서 다루는 그래프는 self-loop나 multiedge가 존재하지 않는 simple graph이다. 어떤 Degree sequence가 주어졌을 때, 이를 만족하는 simple graph가 존재할 조건은 Erdos - Gallai theorem 으로 널리 알려져 있다. 정리 1 (Erdos - Gallai theorem). $d_1 \ge d_2 \ge … \ge d_n \ge 0$ 가 finite simple...
-
동적 계획법을 최적화하는 9가지 방법 (Chapter 2)
동적 계획법을 최적화하는 9가지 방법 (Chapter 2) 이 글은 Chapter 1에서 계속된다. 4. Knuth’s Optimization Recurrence: $DP[i][j] = Min_{i \le k < j}(DP[i][k] + DP[k + 1][j] + C[i][j])$ Condition: $C[i][j]$ is a Monge array, and satisfies $C[a][d] \ge C[b][c]$ for $a \le b \le c \le d$. Naive Complexity: $O(n^3)$ Optimized Complexity: $O(n^2)$ Knuth Optimization은 어떠한 구간을 쪼개는 형태의 동적 계획법을 최적화한다. Optimal Binary Search Tree 라고 알려진 문제를 Knuth가 $O(n^2)$ 동적 계획법으로 해결할...
-
2018 ICPC world Finals C. Conquer the world와 Tree DP optimization
2018년 World Finals에서 어느 팀도 풀지 못했던 문제인 Conquer the world(https://www.acmicpc.net/problem/15691) 문제에 대한 풀이와 사용된 아이디어에 대해 간단히 소개한다. 문제 문제 자체는 굉장히 간단하다. edge마다 이동할 때 드는 cost가 있는 트리가 있고, vertex $i$에 현재 $X_i$명이 있으며 최종 상태에는 적어도 $Y_i$명이 있어야 할 때, 사용해야 하는 cost를 minimize하는 문제이다. Heavy-Light Decomposition 이미 상당히 유명해진 트릭인 heavy-light decomposition에 대해 먼저 간략히 설명하고 넘어갈 것이다. rooted tree에서 heavy edge란, vertex $v$의 자식들 중 가장 subtree의 크기가 큰(vertex...
-
동적 계획법을 최적화하는 9가지 방법 (Chapter 1)
동적 계획법을 최적화하는 9가지 방법 (Chapter 1) 동적 계획법(DP) 알고리즘의 시간 복잡도를 줄이는 기법에 대해서는 다양한 프로그래밍 대회에서 많이 출제된 바가 있다. 이러한 알고리즘은 굉장히 아름다운 방법으로 시간 복잡도를 줄이기 때문에 다양한 대회에서 인기가 많으나, 실제로 표준적인 알고리즘 교과서나 입문서에서 배우기는 힘든 내용이라 초심자가 시작하기 힘든 것이 단점이다. 현재 동적 계획법 최적화에 대해서 배울 수 있는 인터넷 자료들은 대부분 최신 자료가 아니기 때문에, 내가 알고 있는 동적 계획법 최적화 기법을 모두 소개함으로써 이 분야의 지식...
-
2019 ACM-ICPC Seoul Regional 풀이
서론 2019년 2019년 11월 9일 토요일에 ACM-ICPC 서울 리저널이 진행 되었다. 대회에 대한 정보는 http://icpckorea.org 에서 찾아볼 수 있다. (학교 기준으로) 1등은 모든 문제를 해결한 서울대학교의 Cafe Mountain, 2등은 9문제를 패널티 1004분으로 해결한 연세대학교의 Inseop is Korea top, 3등은 9문제를 패널티 1464분으로 해결한 KAIST의 CMD이다. 올해에는 12문제가 출제 되었고, 이 문제들에 대한 풀이를 작성해보려고 한다. A - Fire on Field 문제 $A[0] = 1, A[1] = 1$ 이고, 2 이상의 $i$에 대해, $A[i]$ 를 모든...
-
장애물을 포함하지 않는 가장 큰 직사각형 찾기
장애물을 포함하지 않는 가장 큰 직사각형 찾기 Motivation 계산기하에서 장애물을 포함하지 않는 가장 큰 도형을 찾는 것은 핵심적인 문제 중 하나이다. 다양한 거리계, 그리고 도형의 모양에 따라서 서로 다른 알고리즘들이 존재한다. 예를 들어서, 다음과 같은 문제들을 생각할 수 있다. A) $n$ 개의 점들이 있을 때, 이 점을 포함하지 않으며 넓이가 가장 큰 원은 무엇인가? B) $n$ 개의 점들이 있을 때, 이 점을 포함하지 않으며 넓이가 가장 큰 직사각형은 무엇인가? C) $n$ 개의 점들이 있을 때,...