Table of Contents 개요변환1차 함수 집합 관리최소값 찾기문제 1. 개요 컨벡스 헐 트릭 ( Convex hull trick, Convex hull optimization)은 동적 계획법에서 특정 형태의 점화식이 사용되었을 시 시간복잡도를 획기적으로 줄여주는 기법입니다. DP 관계식을 아래와 같이 정리 가능할 때 사용할 수 있습니다. D[i] 는 어차피 j와 상관이 없기 때문에 상수처럼 취급하고, (i에 대한 함수) * (j에 대한 함수) + (j에 대한 함수) 으로 생각하면 쉽게 컨벡스 헐 트릭의 모양이란 걸 알 수 있습니다. 2. 변환 우선 각각의 j 에 대해 다음과 같은 함수를 생각해봐야 합니다. 여기에서 j 는 정해진 상수이므로 B[j], C[j] 또한 상수입니다. 그러므로 위의 함수..
Table of Contents 개요 트리 펼치기 Mo's algorithm 의 적용 문제 1. 개요 https://www.acmicpc.net/problem/13518 위 문제와 같이 트리에서의 쿼리를 처리할 때, 쿼리의 처리 순서를 마음대로 조작할 수 있다면, DFS로 트리 펼치기 + Mo's algorithm 의 조합으로 시간 복잡도 O( (N+Q) * sqrt N * f(x) ) 을 맞춰 줄 수 있는 경우들이 있습니다. ( * f(x) = 모스 알고리즘에서 노드의 추가 / 삭제 시 필요한 시간복잡도 ) 2. 트리 펼치기 트리에서 DFS를 돌면서, 각각의 DFS 함수가 '시작 했을 때', 그리고 '끝날 때' 해당하는 노드를 배열에 추가해서 트리를 펼치는 스킬입니다. 아래 예시를 통해 알아보겠습니다...