취미로PS하는사람

https://blog.chodaeho.com/posts/2021/splay-tree-1/ Splay Tree 1. 개념과 사용 BST중 하나인 Splay Tree에 대한 설명 blog.chodaeho.com https://blog.chodaeho.com/posts/2021/splay-tree-2/ Splay Tree 2. 시간복잡도의 증명 Splay Tree의 amortized 시간복잡도의 증명 blog.chodaeho.com splay tree 시간복잡도 증명이 궁금해서 둘러보다가 발견했는데 한국어로 잘 설명해놓은 글 같다.

KMP.. 아픈 기억이 있는 알고리즘. 아무튼 그동안 이러저러한 이유로 KMP 공부를 미루고 있다가 최근에야 다시 제대로 배웠다. 아이디어 자체는 간단하다. 문자열 $S$에 패턴 $P$를 매칭할 때, $P$의 $i$번째까지의 문자열에 대해 접두사이면서 접미사인 문자열의 최대 길이(여기서 접두사와 접미사는 원래 문자열을 제외하고 말한다.)를 실패 함수라고 정의한 후 이를 잘 이용하면 $O(|S|+|P|)$에 패턴이 존재하는지 찾을 수 있다. $S$의 중간 부분부터 $i-1$번째까지 문자열과 $P$의 $p$번째까지 문자열이 일치한다고 하자. $S$의 $i$번째 문자를 새로 매칭시키려고 할 때, 만약 성공한다면 $p$를 1 증가시키면 그만이지만 실패할 경우, Naive하게 할 때는 매칭을 시작한 곳 다음 부분..

https://www.acmicpc.net/problem/3121 그 테크닉을 배웠다. (2022.1.5 추가: rotating sweep line 이라고 부르는 것 같다.) $N$개의 점이 있을 때, 특정 기울기의 법선 벡터를 가지는 직선에 점들을 정사영하여 그 순서를 알고 싶다. 만약 Naive하게 구현한다면 각도는 최대 $O(N^2)$개, 점들의 정렬에 대략 $O(Nlog{N})$이 소요될 것이므로 시간이 너무 오래 걸린다. 하지만 잘 생각해보면 정렬된 상태는 법선벡터와 어떤 두 점을 잇는 직선의 기울기가 동일해질 때 그 두 점의 위치만 인접한 상태에서 바뀌기 때문에, 점 쌍들을 기울기로 정렬하여 순서대로 두 점의 위치만 바꾸어주면 모든 $N^2$개의 각도에서 정사영한 순서를 알 수 있다. 각도 정..