Convex hull trick과 Li-Chao tree Convex hull trick은 여러 개의 일차함수들이 있을 때, 어떤 $x$좌표에서의 최댓값 혹은 최솟값을 빠르게 구하기 위해 사용할 수 있는 방법이다. CHT라고 부르기도 한다.일차함수는 다양한 특징을 가져서 비교적 쉽게 관리할 수 있고, 그래서 문제에도 많이 나온다. 일차함수의 최댓값 문제에서 중요하게 사용되는 성질들은 다음과 같다. 1. 여러 일차함수들이 있을 때, 이들의 최댓값을 $m(x)$라고 하면, 각 일차함수 $f(x)$에 대해 $m(x)=f(x)$인 $x$값은 닫힌 구간($\pm\infty$을 포함)으로 표현된다.증명 생략. 2. 일차함수는 볼록하다.$\frac{f(x)+f(y)}{2}=f(\frac{x+y}{2})$이므로 볼록하면서 오목하다. 3. 일차함수들의 최댓값은 볼록하다. 일반.. 더보기 이전 1 ··· 6 7 8 9 10 11 12 ··· 24 다음