특정 DP 문제에서 다음과 같은 꼴의 식을 접할 수 있다.
보통의 경우, 각 (i, j)에 대해 모두 계산해 최솟값을 찾아줘야하므로 시간복잡도는 O(n^2)이다.
하지만 모든 j에 대해 B[j]>B[j-1]인 경우에는 시간복잡도를 O(nlogn)까지 줄일 수 있고
만약 모든 i에 대해 A[i]<A[i+1]이라는 조건까지 더해진다면 시간복잡도를 O(n)까지 줄일 수 있다! (와!)
그 방법이 바로 오늘 게시글에서 다루어볼 CHT이다.
Idea Motivation
A[i]B[j]+C[j]라는 식을 자세히 보면 이 식이 j에 따른 일차함수 식임을 알 수 있다.
즉, n>j이상인 모든 n에 대해서 A[i]B[j]+C[j]를 계산하는 과정은 f(x)=B[j]x+C[j]라는 고정된 일차함수의 A[i]에 대한 함숫값을 계산하는 과정과 같다는 것이다. j번째 직선을 나타내는 함수를 f_j(x)라고 하자.
f_j(x) 들의 기울기인 B[j]가 점점 감소하므로 직선들은 아래와 같이 그려진다.
우리는 각각의 x에 대해 최솟값을 구해주고 싶으므로, 위 그래프에서 빨간 부분만 고려하면 된다.
빨간 부분의 특징은 다음 2가지이다.
① 각 부분은 어떤 f_j(x)에 포함되어있다. (당연!)
② 각 부분을 포함하고 있는 f_j(x)는 x좌표가 증가함에 따라 j의 값도 증가한다.
즉, 위 부분에서도 빨간 부분을 구성하고 있는 함수가 순서대로 j=1, 2, 3, 4, 5일때의 직선임을 알 수 있다.
dp값 구하기
i가 증가함에 따라 dp[i]를 구하기 위해서는 직선을 설정할 수 있어야하며, dp[i]를 구하기 이전까지 설정된 직선들에 대하여 min{f_j(x)}를 구할 수 있어야 한다. 다시 말해 우리는 2가지 쿼리를 O(n) 미만에 수행해야한다.
① 원하는 x값에 대해 f_j(x)의 최솟값 구하기
f_j(x)를 최소로 만드는 j를 구한다면, f_j(x)의 식을 통해 함숫값을 계산할 수 있다.
빨간 부분의 두 번째 특징을 이용하면, 이분탐색을 통해 f_j(x)가 최소가 되는 j를 구할 수 있다.
이웃한 직선들의 교점의 x좌표와 현재의 x값을 비교함으로써 앞으로 어떻게 값을 조정해나가야 하는지 알 수 있다.
top을 현재 설정되어있는 직선의 개수, F를 직선을 표현하는 구조체일때 코드는 아래와 같이 작성된다.
(F.a는 직선의 기울기, F.b는 직선의 y절편, cross(F[mid], F[mid+1])는 mid번째 직선과 mid+1번째 직선의 교점의 x좌표를 나타낸다.)
ll query(ll x)
{
int l=0, r=top-1;
while (l<r) {
int mid=(l+r)/2;
if (cross(F[mid], F[mid+1])<x) l=mid+1;
else r=mid;
}
return F[l].a*x+F[l].b;
}
이 때의 시간복잡도는 O(logn)이다.
만약 구하고자하는 x값이 계속 증가한다면, f_j(x)를 최소로 만드는 j의 값도 증가하기 때문에 j의 값에 대한 스위핑을 해줄 수 있고, 이 경우 알고리즘 전체에 걸쳐 시간복잡도가 O(n)이 되므로 유사 O(1)에 쿼리를 해결할 수 있다. 이러한 경우가 바로 가장 위에서 소개했던 A[i]<A[i+1]인 경우이다.
② 새로운 직선 추가하기
기울기가 계속 감소하고 있으므로 가장 뒤에 직선을 하나 더 추가해주면 된다.
이렇게 끝나면 좋겠지만, 한 가지를 더 고려해주어야 한다.
이 그림은 위 그림에서 새로운 직선 f_6이 추가되었을 때 그림이다.
(기울기는 계속 감소하기만 하면 되기 때문에 음수가 되어도 문제는 없다.)
위 그림에서 빨간 부분을 갱신하면 위와 같이 그려져있는데, f_5가 빨간 부분에 더 이상 관여하지 않게 되었다는 것을 눈으로 확인할 수 있다. 이처럼 새로운 직선이 추가됨으로써 기존에 있던 직선이 무의미해질 수 있는데, 이러한 직선을 제거해주는 작용이 필요하다. 직선들을 인덱싱하는 과정과 pop 및 push_back 하는 과정을 모두 수행해야하기 때문에 직선 을 배열에 저장하여 처리하는 것이 가장 편하다.
top을 현재 설정되어있는 직선의 개수, F를 직선을 표현하는 구조체일때 기울기가 x, y절편이 y인 직선을 추가하는 코드는 아래와 같이 작성된다. (F.a는 직선의 기울기, F.b는 직선의 y절편, cross(F[p], F[p+1])는 p번째 직선과 p+1번째 직선의 교점의 x좌표를 나타낸다.)
void line_insert(ll x, ll y)
{
F[top].a=x, F[top].b=y;
while (top>1) {
if (cross(F[top-1], F[top])<cross(F[top-2], F[top-1])) {
F[top-1]=F[top];
top--;
}
else break;
}
top++;
}
cross(F[top-2], F[top-1])은 빨간 부분 상에서 top_2번째 직선과 top-1번째 직선의 교점의 x좌표로,
빨간 부분 상에서 F[top-1]에 포함되는 영역이 시작되는 x값을 말한다.
똑같이 cross(F[top-1], F[top])은 빨간 부분 상에서 top번째 직선이 추가되었을 때
빨간 부분 상에서 F[top]에 포함되는 영역이 시작되는 x값이다.
그런데 만약 F[top]이 F[top-1]보다 먼저 시작한다면?
이는 F[top-1]이 무의미한 직선이 되었다는 이야기이고, 이 직선을 pop해준다.
모든 직선은 최대 1번 삽입되며 최대 1번 pop되기 때문에 시간복잡도는 O(n)이다.
문제 해결 순서
① 당연히 dp임을 먼저 깨달아야한다.
② 위에 있는 식의 꼴로 만들어 A, B, C, D를 구한다.
문제에 따라서 B가 증가함수이며 min이 아닌 max를 구하는 문제도 있는데, 똑같이 구현하면 된다.
당연히 dp 식을 처음 세웠을 때는 저런 꼴이 나오지 않는다.
식 정리를 통해서 i, j로 이루어진 항들을 분리하여 저 꼴을 만들어주면 된다.
예를 들어 설명하면 좋으니, 감이 오지 않는 사람들은 아래 예시 문제들을 설명한 글을 보면 좋을 것이다.
③ B가 감소/증가하는 꼴인지 확인한다. 만약 아닐 경우 감소하도록 만들어줄 수 있는지 확인한다.
(B가 감소하도록 전처리를 해주어야 하는 대표적인 문제 : 조명등 [BOJ 19943] / 땅따먹기 [BOJ 6171])
④ 열심히 코드를 짠다! 직선 추가 및 함숫값 계산을 통해 원하는 dp 값을 구한다.
CHT 주의할 점
당연한 이야기이겠지만 문제마다 다르다.
하지만 코딩을 하면서 느낀 공통적으로 CHT 문제를 풀며 주의해야 할 점은 다음과 같다.
① 0번째 직선의 유무
CHT를 하며 dp[0]에 대한 설정은 문제마다 다른데, dp의 정의에 따라 0번째 직선이 포함되어야 하는 경우도 있고, 포함되지 않아야하는 경우도 있다. 이는 CHT의 작동 방식과 해당 dp를 완전히 이해하고 있어야 완벽하게 판정할 수 있다.
그러니 CHT를 이용한 문제를 풀 때는 작은 케이스에 대해 손으로 시뮬레이션을 해보며 프로그램이 어떻게 실행되는지를 깊이 이해한 후 0번 직선의 필요성을 판단해야한다.
② cross 함수의 작성
double cross(line x, line y) { return (double)(y.b-x.b)/(x.a-y.a); }
한 줄이면 되는 간단한 함수임에도 잘못 짤 수 있다.
친구가 cross 함수 짤 때 조심하라고 하길래 속으로 "에이 이걸 누가 틀려"라고 생각했는데
바로 다음 CHT 문제를 풀 때 내가 틀렸다... 저 식을 아예 외우는 것도 나쁘지 않을 것 같다.
③ 맞왜틀에 좌절하지 말기
CHT 문제를 풀면 다른 문제들과는 다르게 한 번에 맞은 기억이 거의 없다. 항상 몇 번의 WA를 받은 후에야 AC를 받는다. (물론 이는 필자가 가지고 있는 구현장애도 한 몫을 하지만) 다른 유형의 문제보다 더 심한 것 같다.
그만큼 CHT라는 기법을 사용하는 것 자체가 실수를 유도할만한 부분이 많다는 이야기이다.
①, ②가 이유가 될 수도 있고, 식 정리에서 실수가 있을 수도 있다. 이렇게 맞왜틀이 나더라도, 식 정리를 다시 하거나 시뮬레이션을 직접 해보는 방법을 통해 절대 좌절하지 말고 침착하게 오류를 찾는 것이 중요하다!
CHT 연습문제
특공대 [BOJ 4008] (P1 & Class7)
APIO 2010 기출문제, CHT를 사용하는 가장 대표적인 문제이다.
문제 링크 : https://www.acmicpc.net/problem/4008
풀이 링크 : 추후 포스팅 예정
땅따먹기 [BOJ 6171] (D5 & Class8)
원래 P1이었는데 얼마 전에 D5로 올라버린 문제이다.
CHT를 써야한다는 사실은 관찰하기 쉬운데, 막상 쓰려고 하면 전처리가 조금 필요한 문제이다.
문제 링크 : https://www.acmicpc.net/problem/6171
풀이 링크 : 추후 포스팅 예정
나무 자르기 [BOJ 13263] (P2 & Class7)
CHT에 대해 아직 완전히 이해하지 못했다고 생각하는 사람들에게 추천한다.
식 정리도 많지 않고 CHT를 가장 직관적으로 사용하는 문제이다.
문제 링크 : https://www.acmicpc.net/problem/13263
풀이 링크 : 추후 포스팅 예정
조명등 [BOJ 19943] (D5)
따끈따끈한 KOI 2020 1차 대회 기출문제!
문제 링크 : https://www.acmicpc.net/problem/19943
풀이 링크 : 추후 포스팅 예정