Convex hull trick의 시간에 따른 관리
Convex Hull Trick의 시간에 따른 관리
Introduction
Dynamic programming은 많은 문제에서 등장하는 풀이 방법이다. Convex hull trick은 $O(n^2)$ 시간복잡도를 $O(n log n)$으로 줄여주는 등 획기적인 시간 단축을 이루어내는 dynamic programming에 대한 최적화 방법이다. 이번 글에서는 시간에 따른 convex hull의 관리에 대해 알아본다. Persistent convex hull과 convex hull rollback에 대해서 알아보자.
1. Persistent Convex Hull
문제 상황
$n$개의 직선 $f_i(x) = a_ix + b_i$가 주어진다. 직선들의 기울기 $a_i$는 증가하는 순서로 주어진다. 쿼리로 주어진 $t$, $k$에 대해서 $max_{i=1}^t f_i(k)$를 구해야 한다.
알고리즘 설계
1단계: 트리 구조로 관계 보존
스택 연산의 본질을 생각해보자. 직선 A가 스택에 있을 때 직선 B가 추가되면, B는 A의 “후계자” 역할을 한다. 이 관계를 트리로 표현한다. 각 직선을 정점으로 하고, 스택에서 직접적인 앞-뒤 관계에 있던 직선들을 부모-자식 관계로 연결한다.
중요한 성질: 시점 $t$에서의 hull은 해당 시점의 “마지막 직선”에서 루트까지 올라가는 경로와 정확히 일치한다.
2단계: 구간 정보의 관리
각 직선이 hull에서 최적이 되는 $x$ 구간을 알아야 한다. 직선 $f$가 구간 $[L, R]$에서 최적이라면, 쿼리 $x$가 이 구간에 속할 때만 $f$가 답이 된다. 트리에서 각 노드는 (직선, 구간의 시작점)을 저장한다. 루트에서 어떤 노드까지의 경로를 따라가면서, 각 노드의 구간 시작점들을 보면 단조증가하는 수열을 이룬다.
3단계: 쿼리 처리의 논리
시점 $t$, 위치 $k$에 대한 쿼리가 주어졌을 때:
- 시점 $t$에서의 마지막 직선 $s_t$를 찾는다
- $s_t$에서 루트까지의 경로에서, 구간 시작점이 $k$ 이하인 직선들을 찾는다
- 이 중 가장 깊은 위치에 있는 직선이 답이다
왜 가장 깊은 위치인가? 경로를 따라 올라가면서 구간 시작점들이 단조증가하므로, $k$ 이하인 마지막 지점이 바로 $k$를 포함하는 구간의 시작이기 때문이다.
4단계: Binary Lifting을 통한 최적화
경로를 하나씩 따라가면 $O(n)$ 시간이 걸린다. 이를 binary lifting으로 최적화한다. 각 노드에 대해 $2^j$번 위로 올라간 조상과 조상의 구간 시작점을 미리 계산해둔다. 쿼리할 때는 이 정보를 이용해 $O(log n)$ 시간에 적절한 조상을 찾을 수 있다.
복잡도: 전처리 $O(n log n)$, 쿼리 $O(log n)$, 공간 $O(n log n)$
2. Convex Hull Rollback
문제 상황
직선이 추가되거나 가장 마지막에 추가한 직선이 제거된다. 제거되지 않고 남아있는 직선들의 기울기는 항상 추가된 시점에 대해 오름차순이다. 직선을 추가/삭제 하는 과정에서 쿼리로 $x=k$에 대한 최댓값을 구해야 한다.
핵심 아이디어: 상수 시간 rollback
일반적인 convex hull trick에서 직선을 추가할 때는 기존 직선들을 제거하는 과정이 있다. Naive하게 직선을 제거하고 rollback 과정에서 다시 추가해주면 쿼리당 최대 선형 시간복잡도를 가지게 된다. 중요한 것은 제거되는 직선을 모두 추적하는 것이 아니라, 스택의 크기를 줄이는 것과 같은 효과를 배열을 사용해서 $O(1)$에 할 수 있다는 것이다.
알고리즘 설계
1단계: 상태 정의
Hull을 배열로 관리한다. hull[1..sz]가 현재 hull을 구성하는 직선들의 배열이다. 핵심 상태는:
hull[]: 직선을 저장할 수 있는 길이 $n$의 배열 ($n$은 전체 삽입되는 직선의 개수)sz: 현재 유효한 직선의 개수
2단계: 변화 기록
각 추가 연산에서 정확히 어떤 변화가 일어나는지 기록한다:
- 이전
sz값 - 덮어쓰여진 배열 원소의 이전 값
이 정보만 있으면 연산을 정확히 되돌릴 수 있다.
3단계: 제거 과정의 논리
새로운 직선 $f$를 추가할 때:
- 이분탐색을 통해 $f$에 의해 불필요해지는 직선들의 개수를 구한다
sz를 감소시켜 convex hull에서 직선들이 pop되는 효과를 생성한다- $f$를
hull[sz]에 추가한다
연속된 세 직선 $a$, $b$, $c$가 있을 때, $b$가 불필요한 조건은 $a$와 $c$의 교점이 $a$와 $b$의 교점보다 왼쪽에 있는 경우이다.
4단계: 쿼리 처리
현재 hull에서 $x=k$일 때의 최댓값을 구한다. Hull의 직선들은 convex하게 정렬되어 있으므로, 이분탐색으로 최적 직선을 찾을 수 있다.
알고리즘의 정확성
왜 rollback이 O(1) 시간에 가능한가? 각 추가 연산에서 변하는 상태가 상수 개(sz와 hull의 원소 1개)이므로, 이를 복원하는 것도 상수 시간에 가능하다.
복잡도: 직선 추가 $O(log n)$, 직선 제거 $O(1)$, 쿼리 $O(log n)$, 공간 $O(n)$
3. 적용 문제
Persistent Convex Hull
- BOJ 33611 - 뗏목 제작: 기울기가 일정 값 이하인 직선의 convex hull에서 쿼리를 처리해야 하는 문제
Convex Hull Rollback
- BOJ 3319 - 전령들: 트리에서 DFS를 하면서 경로상의 점들에 대한 convex hull을 관리해야 하는 문제. DFS 백트래킹 시 hull도 함께 rollback해야 한다.
마무리
변하는 시간에 따라 convex hull을 관리하는 2가지 방법을 살펴보았다:
- Persistent Convex Hull: 과거의 모든 상태를 보존하여 임의 시점 조회 가능
- Convex Hull Rollback: 현재 상태만 유지하되 이전 상태로 되돌리기 가능
두 방법 모두 convex hull의 구조적 성질을 유지하면서도 시간적 변화를 효율적으로 관리한다는 공통점이 있다. 문제의 특성에 따라 적절한 방법을 선택하여 사용하면 된다.