나름 개발자의 IT블로그

Splay Tree는 Balanced Binary Search Tree의 한 종류로 데이터의 삽입, 삭제, 탐색을 $O(\log N)$에 준하는 속도로 처리할 수 있도록 하는 자료구조이다. 보통 학부과정에선 저런 기본 연산들을 배우게 되는데 Splay Tree를 사용해야만 해결할 수 있는 알고리즘 문제에서는 극한의 테크닉을 사용하여 많은 쿼리를 처리할 수 있다. 이 글에서는 Splay Tree가 어떤 자료구조인지 소개하기보다는 해결할 수 있는 application을 중점으로 소개한다. Splay Tree는 1985년에 Self-Adjusting Binary Search Tree라는 논문으로 소개가 되었고 여기에도 Tarjan이 저자로 들어가있다. 정말 많은 공헌을 하신 분이다. BasicSplay Tre..

연습용으로 예전 Contest에 버추얼참가를 했다. 아쉽게도 4솔에 실패했다. A - Two Subsequences [Solved!] 문자열 $s$가 주어지고 그 문자열을 $a, b$인 두 개의 문자열로 나눌건데 $a$는 사전순으로 가장 앞서는 문자열, $b$는 $s$에서 $a$를 제외한 문자열인 조건이 있을 때 나눠진 문자열들을 출력하는 문제이다. $a$는 $s$에서 사전순으로 가장 앞서는 문자 하나이면 충분하다. 예를들어 $s = ``helloworld"$일 때 $a = ``d"$이고 $b =``helloworl"$이 된다. B - Divine Array [Solved!] 배열 $a$가 주어지고 그 배열에 연산을 여러번 하려고 할 때 $k$번 연산을 수행한 후 $x$번째 위치의 수를 묻는 문제이다. ..