생각날때마다 올리는 블로그

서론우리는 많은 쿼리 문제를 만나게 된다. 특히, 그 중에서도 구간을 처리하는 쿼리문제는 많이 나오면서도 중요한데, 이를 일반적으로 naive하게 처리하면 망한다(...)예를 들어, 구간의 최소값을 구하는 문제가 있다고 하자. 이 경우, 일반적으로 짜면 모든 구간을 다 돌면서 확인하는 식일건데, 쿼리의 개수를 Q라고 하고, 구간의 최대 길이를 N이라고 하면 O(QN)의 시간이 소요된다. 하지만, Q가 10만, N도 10만으로 주어지는 일반적인 문제에서는 TLE로 코드가 터지고 내 멘탈도 터지고(...)어찌됐든, 다른 방안을 모색해야한다. 이 때 사용하는 것이 세그먼트 트리이다. 우리는 세그먼트 트리에 대해 자세히 알아보고, 일반적인 재귀로 짜는 방식 말고 비재귀로 짜는 방식에 대해 알아보겠다. ( 개인적..

https://oj.uz/problem/view/JOI18_stove 풀이a[i]-(a[i-1]+1)이 공백기이다.공백기를 가장 작은 순서대로 N-K개 가지고 있으면, 이는 최소시간이 된다.또한, 무조건 사람이 왔을때 켜야 되므로, N명이 있으면 최소 N의 시간이 걸린다.ans=N으로 잡고 priority_queue로 관리해주면 된다. 코드https://oj.uz/submission/49483

서론우리는 종종 트리에서 u점과 v점의 거리 차이를 구하는 문제를 접하게 된다. 문제가 하나라면 순회하면서 찾아내면 되지만, 만약 쿼리로 주어진다면...? naive하게 짜다간 뚝배기가 깨진다.따라서, 우리는 naive가 아니라 다른 방법을 찾아내야한다. 이 때, 우리는 하나의 중요한 점을 관찰할 수 있다. 바로, u와 v의 거리는 u와 v가 동시에 가르키는 공통 조상(Common Ancestor)과 관련이 있음을 알 수 있다. 그러면, 우리는 각 점에서 트리의 시작노드에서 그 노드까지의 거리를 저장해놓고, 공통조상까지의 거리를 구해서 빼면 됨을 알 수 있다. 그러면, 공통 조상은 어떻게 구할까? 이걸 지금 알아보도록 하자. 필요한 사전지식구간 트리(흔히 Segement tree,세그먼트 트리라고 불림)..