구사과

http://poj.org/problem?id=2104https://www.acmicpc.net/problem/7469 1. Naive - O(MNlgN)더 이상의 자세한 설명은 생략..O(N) Selection Algorithm이 있지만 느리면 느렸지 빠르진 않을 듯.여담으로, 잘 컷팅하면 이걸로 2번보다 빠르게 풀수 있다 ㅡㅡ; 2. Query Sorting - O(NlgN + M*N^0.5*lgN)http://amugelab.tistory.com/entry/%EB%A3%A8%ED%8A%B8-%EC%95%BC%EB%A7%A4때문에 역시 자세한 설명은 생략.간단히 설명하자면, 맨 처음 좌표압축을 한 다음에 링크 1번 트릭 + K번째 원소 BIT를 구현해 주면 된다.시간이 간당간당한 편이다.. 버킷 사이..

pdf로 대신한다.

꼭 이걸 써야 되는지 써도 되는지는 모르겠다 공개적인 곳에서 자랑하는 것도 아니고, 그래도 이런 경험을 해볼 일이 얼마나 될라나 싶어서 여기다 대강 글로 적어 남기고 싶다. 사실 겨울학교 전까지만 해도 내가 잘하는 지도 몰랐고 국대에 대한 욕망도 별로 없었는데 (기대치가 없으니), 와서 보니까 내가 생각보다 잘하더라. 겨울학교 끝날 때 시험을 치고 대강 6등? 언저리에 머물렀더니 확실히 유혹이 생겼다. 딱히 잘본것도 아닌데 그렇다고 딱히 못 본것도 아니고 그 점수대가 다 비슷비슷해서. 꼴지를 해도 공부야 했겠지만 그래도 목표치를 조금 높게 잡아보기로 했다. 그런다고 죽는것도 아니고 ㅎㅎ 겨울학교 갔다오고 배운게 참 많다.. 세그먼트 트리를 짤 수 있게 된 것도 사실상 그 이후였고, 컨벡스헐트릭도 몇달만에..