The Story of Joon

Link/Cut Tree (2) 다음 자료들을 참고했다. * 위키피디아 링크 * MIT Lecture Note Link/Cut Tree를 이해하거나 구현하기 위해서는 먼저 Splay Tree에 대한 이해가 필요하다. Splay Tree에 대한 내용은 여러 곳에 잘 설명되어 있다. Link/Cut Tree는 여러 개의 트리를 관리하는 자료구조이다. 이 자료구조의 특징은, find_root(노드가 속한 트리의 루트), link(한 트리의 루트를 다른 트리의 노드로 연결), cut(루트가 아닌 노드와 부모 사이의 연결 제거) 연산을 모두 amortized $O(\log N)$의 복잡도에 수행이 가능하다는 것이다. 앞서 말했듯이 LCT는 여러 개의 트리로 되어있는데, 이 각각의 트리를 represented tr..

cubelover님의 블로그를 많이 참고했다. Splay Tree에 대한 설명은 이 블로그로 가면 많은 도움이 된다.

※ Pintos 기본 세팅: http://topology-blog.tistory.com/2 핀토스를 학교에서 시켜서 하게 된다면 아마 학교에서 교수님이나 조교님 등이 도움을 많이 주시겠지만, 미리 해본다든가 하는 이유로 따로 하는 경우도 있을 것이다. 핀토스와 같은 프로젝트를 해본 경험이 있다면 잘 헤쳐나가겠지만, 그러지 않은 경우 처음에 많은 어려움을 겪게 될 가능성이 높다. 필자 역시 그랬다. 그래서 이 포스트는 그러한 사람들, 그리고 필자 본인을 위한 포스트이다. 프로젝트별 팁은 포스트를 따로 남긴다. 여기서는 프로젝트를 전반적으로 어떤 점을 유의해야 하는지에 대한 필자의 생각을 다룬다. 사람마다 의견은 다를 수 있으며, 여기에 쓰인 내용은 그저 참고용으로 봐주셨으면 좋겠다. 1. Project D..