???한 자료구조, 알고리즘 모음

2018. 9. 9. 19:50CS 이론/자료구조

아직 공부중인 자료구조 / 알고리즘들이다.

세상에 똑똑한 사람이 너무 많아..


1. DP tricks


1.1. Alien Trick (Wang Qing-Shi Binary Search)


구사과 블로그

imeimi 블로그

원문을 구할 수 있는 곳 (중국어)


IOI 2016 Aliens

NAIPC 2017 Blazing new trails


1.2. dynamic CHT (without pointer)


일명 성적CHT. 본지가 언제인데 아직도 못 짜냐 ㅡㅡ


1.3  Li-Chao tree

 Doc2

 csacademy 연습문제



2. Offline Dynamic Tricks


2.1. Offline Dynamic Connectivity


2.2. Dynamic MST


2.3. Old Driver Tree

(But now I call it Chtholly tree~)


2.4. TreeMO


3. 자료구조


3.1. Segment Tree Beats


중국의 국대 후보들은 전부 국대 선발에 반영되는 알고리즘 소논문을 쓴다고 한다. ㄷㄷㄷㄷ

이것도 그 중 하나.


3.2. Link - Cut tree


3.3. van Emde Boas tree,

     x-Fast trie, y-Fast trie


4. Graph, Flow


4.1. Manhattan MSTEuclidean MST


4.2. Gomory-Hu tree


더민규 팀노트에서 봤다. 아직은 ??????의 영역.


4.3. Dominator Tree


4.4. L-R maxflow

- koosaga님의 연습문제들


4.5. Incremental SCC


- dynamic & offline trick에 들어가야 할 것 같기도 하다.


4.6. Borukva's algorithm


4.7. Biconnected Component


4.8. Counting Spanning Forest


4.9. Karger's algorithm


4.10. Tutte's theorem


5. 기하


5.1. Voronoi Diagram, Delaunay triangulation


5.2. Plane Matching


5.3. Dynamic management of the Convex Hull


6. String


6.1. EERTREE

medium 설명글


APIO palindrome이나 RUN contest의 queryreuq를 풀기에 최적화된 자료구조라고 한다. 꾸사가님이 되게 좋아하는 자료구조인 것 같은데 난 어렵다...


6.2. Aho-Corasick


6.3. Suffix Array & LCP array

- cubelover님의 구현체

- in Linear complexity


6.4. Suffix automaton


7. Mathematics


7.1. Power Series Beats


왜 다 Beats인가 했더니 angel beats라는 애니메이션이 있단다 ㅡㅡ


7.2. Kirchhoff's theorem


'CS 이론 > 자료구조' 카테고리의 다른 글

Persistent Data Structure  (0) 2018.10.11
???한 자료구조, 알고리즘 모음  (4) 2018.09.09
  • 프로필사진
    탐레프가되고싶어요2018.08.08 22:55

    스팸아님

    https://arxiv.org/pdf/1210.4594.pdf
    https://arxiv.org/pdf/1705.11035.pdf
    https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1367&context=cstech
    https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
    https://arxiv.org/pdf/1105.2397.pdf
    http://www.dtic.mil/dtic/tr/fulltext/u2/a093097.pdf
    http://i.stanford.edu/pub/cstr/reports/cs/tr/81/875/CS-TR-81-875.pdf
    http://tmc.web.engr.illinois.edu/ch3d/ch3d.pdf
    http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.436.9750&rep=rep1&type=pdf
    https://u.cs.biu.ac.il/~liamr/p723-holm.pdf
    https://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf

  • 프로필사진
    아이 엠 유얼 빅 팬2018.08.09 01:57

    아임 유얼 빅 팬!!!
    So god TAMREF

  • 프로필사진
    I am your bigfan2018.08.09 01:58

    I am your bigfan!!

    갓레프

  • 프로필사진
    diuven2018.08.20 20:07

    이것도 넣어주세요~
    https://en.wikipedia.org/wiki/Quad-edge