티스토리 뷰

Convex Hull Optimizaiton 중에 추가되는 직선의 기울기에 경향성이 없다면, 직선들을 스택으로 관리하지 못하고, set으로 관리하여 lower_bound 같은 연산을 잘 활용해주어 해결해야 한다. 그런데 이렇게 코딩하는 것은 여간 쉬운 일이 아니다.

 

실제로 Convex Hull Optimization을 사용하는 DP 문제는 아니지만, 이런 상황을 잘 표현해주는 예시 문제(반평면 땅따먹기)로 설명을 이어가겠다.

 

직선들을 set으로 관리하는 방법으로 위 문제를 해결하면 코드는 다음과 같이 되며, 꽤나 복잡하다.

더보기

 

Segment tree를 이용하여, 직선들을 관리해주어 128비트 정수형과 실수형 변수 없이 효과적으로 이 문제를 해결할 수 있는 Li Chao tree에 대해 알아보자.

 

Li Chao tree는 Segment tree에서 정점을 동적으로 만들어가며, 각 구간마다 제일 의미 있는 직선에 대한 정보를 가지고 있는 Segment tree의 응용이라고 볼 수 있다. 질의로 들어올 수 있는 x 좌표의 범위가 [S, E]라고 할 때, Li Chao tree의 루트 정점은 구간 [S, E]를 관리한다.

 

Li Chao tree의 구간 [s, e]를 대표하는 어떤 정점에 직선 $y = ax + b$를 갱신하는 상황을 보자. $x = s$일 때 직선의 y 좌표의 값이 낮은 직선을 low, 큰 직선을 high라고 보면 다음과 같이 3가지 상황이 있을 수 있다.

 

상황 1. 구간 [s, e]에서 high가 모두 큰 경우

이때, 정점의 직선을 high로 바꿔주고, 더 이상의 추가 작업은 없다.

 

상황 2. low와 high의 교점이 왼쪽에 있는 경우

이 경우 low 직선이 [s, e] 구간의 대부분에서 큰 값을 가지므로 정점의 직선을 low로 바꿔주고, 왼쪽 구간의 정점에 high를 갱신해주는 작업을 재귀적으로 이어나간다.

 

상황 3. low와 high의 교점이 오른쪽에 있는 경우

마찬가지로, 이 경우 high 직선이 [s, e] 구간의 대부분에서 큰 값을 가지므로 정점의 직선을 high로 바꿔주고, 오른쪽 구간의 점점에 low를 갱신해주는 작업을 재귀적으로 이어나간다.

 

직선이 추가되는 경우 위와 같이 Segment tree에 갱신 작업을 이어나가는 경우, 전체 구간 [S, E]의 크기를 $X$라 할 때, 시간복잡도는 최대 $O(\lg X)$가 된다.

 

어떤 x 좌표 $x$에 대해 가장 큰 $y$ 값을 구하고 싶다면, top-down 방식으로 정점의 직선 $y = ax + b$에 $x$ 값을 넣어 $y$ 값을 구하고, 방문하는 정점 중 가장 큰 $y$ 값을 구하면 된다. 이때 시간복잡도 또한 $O(\lg X)$가 된다.

 

구현은 다음과 같이 할 수 있다.

더보기

 

예시 문제의 경우 질의로 주어지는 $x$ 좌표가 정수이므로, 정수에 맞춰 구현을 했다. 만약, 질의로 실수가 들어오는 경우는 Segment tree 구현을 다르게 해야 한다. 만약, 최댓값을 구하는 게 아니라, 최솟값을 구하고 싶은 경우, 이와 비슷한 방식으로 새로 구현하거나, 위 코드에서 넣는 직선의 기울기와 y절편 값을 negation 하는 것으로 간단하게 구할 수 있다.

 

* 응용 방법

기존에는 stack이나 set을 이용했지만, Li Chao 트리에서는 Segment tree를 이용하므로, Persistent Segment tree와 같은 응용 버전을 생각해볼 수 있다. 이런 문제를 아직까지 실제로 본 적은 없다.

'공부' 카테고리의 다른 글

Z-function  (2) 2021.03.08
Li Chao Tree (Dynamic Convex Hull Optimization)  (0) 2021.03.08
Stern-Brocot 트리  (0) 2019.05.21
트리의 지름 구하기  (5) 2016.10.11
Convex Hull Optimization  (4) 2016.08.23
가장 먼 두 점 구하기  (6) 2016.07.17
댓글
댓글쓰기 폼