구사과

(2017.10.01 초판)(2018.01.27 문제집 추가)내가 만든 문제집을 내가 찾기 힘들어서, 정리하고자 만들었다. 이렇게 돌아보니까 근본 없다.. 전부 소개하기는 아까우니까, 별점 붙여서 별점 높은 것만 소개. convex hull trick https://www.acmicpc.net/workbook/view/476 (★★★★)컨벡스 헐 트릭 연습 문제집. 난이도는 쉽지 않다.FFT https://www.acmicpc.net/workbook/view/824 (★★★★★)FFT 연습 문제집. 이것도 쉽지 않다. FFT 쓰는 문제를 거의 전부 모은 것 같다.Segtrees are too mainstream https://www.acmicpc.net/workbook/view/912 (★★★★☆)Spl..

POI 2009/2010. Pilots$N$개의 수가 주어질 때, 연속 구간 중 (구간 내 최댓값) - (구간 내 최솟값) $\leq T$를 만족하는 최대 길이의 연속 구간을 찾는 문제이다. $N \leq 3000000$을 만족한다.데큐를 사용해서 Sliding window로 구간 최댓값 / 최솟값을 구하는 알고리즘이 잘 알려져 있다. 이 알고리즘에 inchworm을 적용하여서 문제를 해결할 수 있다. 처음에 [1, 1] 구간에서 시작하여. (최댓값) - (최솟값) $ \leq T$ 를 만족할 때까지 구간의 끝점을 늘린다. 더 이상 늘릴 수 없으면, 시작점을 늘리면서 계속한다. 이러한 식으로 구간의 길이를 최대화하면서 데큐를 관리해 주면 최대 구간의 길이를 알 수 있다. 고려대학교 2017 경시대회. L..

1. 제로스택을 구현하면 되는 단순한 문제입니다. 2. 공항비행기가 올 때 공항 게이트를 골라야 하는 데, 각 상황에서 고를 수 있는 공항 게이트 중 가장 큰 것을 골라야 한다는 그리디 접근을 생각해 볼 수 있습니다. 그 위치를 비워두면서 도착하는 비행기의 수를 늘릴 수 없기 때문입니다. ($i$번째 비행기가 비워둔 자리가 끝까지 비었다면 비우는 의미가 없으니 모순입니다. 그렇지 않다면, 비워둔 자리를 다른 비행기 ($j$번째, $j > i$)가 채울 것인데, 그렇게 하느니 $i$번째 비행기와 위치를 바꾸는 것이 이득입니다. 이런 식으로 계속 진행하면 그리디 알고리즘이 최적임을 증명할 수 있습니다.) 이 알고리즘을 그대로 구현하면 $O(PG)$ 시간이 걸려 시간 초과가 납니다.이를 해결하는 방법은, st..