반응형 [C++로 배우는 알고리즘과 자료구조 심화] Day 16: DP 최적화 기법 (Convex Hull Trick, Divide and Conquer Optimization) DP 최적화 기법동적 계획법(DP)은 많은 문제를 효율적으로 해결할 수 있는 강력한 도구입니다. 그러나 때로는 DP의 시간 복잡도를 더 최적화할 필요가 있습니다. 오늘은 두 가지 주요 DP 최적화 기법에 대해 학습하겠습니다: Convex Hull Trick과 Divide and Conquer Optimization.Convex Hull TrickConvex Hull Trick은 주로 함수 (y = ax + b)의 최솟값이나 최댓값을 효율적으로 찾는 문제에서 사용됩니다. 이 기법은 선형 함수들의 집합을 유지하고, 각 쿼리마다 특정 (x)에서의 최소 (y) 또는 최대 (y)를 빠르게 계산합니다.문제 예시다음과 같은 문제를 고려해봅시다:주어진 선형 함수들의 집합 ({y = a_1x + b_1, y = a_2x.. 2024. 8. 1. 이전 1 다음 반응형
