|
이 책으로 공부하는 법
문자열 고급 Aho-Corasick 1. 아호–코라식 자동자 — 패턴을 트라이 하나에 담고 실패 링크로 글자마다 갈 노드를 정해 두면 검색이 패턴 수와 상관없이 텍스트를 한 번만 읽는 이유 Suffix Array + LCP 2. 접미사 배열 — 접미사를 사전순으로 늘어놓아 두면 한 패턴으로 시작하는 접미사가 한 구간에 모이는 이유 Suffix Automaton / Suffix Tree 3. 접미사 트리 — 원문의 접미사를 모두 라딕스 트리에 담아 두면 패턴이 나타나는 자리가 패턴을 따라 내려간 노드 하나 아래에 모이는 이유 자료구조 고급 Lazy Propagation Segment Tree 4. 지연 전파 세그먼트 트리 — 구간을 덮는 노드에 갱신을 적용하고 아래로는 미뤄 두면 구간 갱신과 구간 접기가 함께 노드 몇 개로 끝나는 이유 Persistent Segment Tree 5. 영속 세그먼트 트리 — 바뀐 자리로 가는 길의 노드만 새로 지으면 모든 버전을 남기고도 고치기와 구간 접기가 노드 몇 개로 끝나는 이유 정렬 다중집합 / 순위 질의 6. 다중집합 — 원소 수를 노드에 적어 두면 같은 원소가 몇 벌이든 개수 세기가 트리 높이만큼으로 끝나는 이유 7. 순서 통계 트리 — 노드마다 부분트리의 원소 수를 적어 두면 순위와 위치를 내려가는 길 하나로 서로 바꾸는 이유 자가 균형 BST 8. 트립 — 키는 이진 탐색 트리 순서로, 난수 우선순위는 힙 순서로 두면 어떤 입력에도 깊이의 기댓값이 로그인 이유 9. 스플레이 트리 — 접근한 노드를 아래에서 두 층씩 끌어올리면 호출 하나는 길어도 원소 수가 그대로인 트리에서 접근 한 번의 상각 비용이 로그에 묶이는 이유 10. 레드-블랙 트리 — 빨강을 잇달아 두지 않고 검은 노드 수를 맞추면 높이가 2 log₂(n+1) 을 넘지 않는 이유 11. AVL 트리 — 어느 노드에서든 두 부분트리의 높이 차를 1 이하로 두면 높이가 원소 수의 로그에 묶이는 이유 12. 희생양 트리 — 치우친 부분트리를 통째로 다시 지어 두면 찾기는 호출마다, 넣기와 지우기는 평균이 로그 안에 드는 이유 13. 2-3 트리 — 넘친 노드의 가운데 원소를 부모로 올려 나누면 모든 잎이 같은 깊이에 남는 이유 14. 카테시안 트리 — 새 값은 늘 오른쪽 경계의 끝에 붙으므로 그 경계를 스택으로 들면 수열을 한 번 읽어 트리가 다 지어지는 이유 디스크 지향 트리 (B/B+) 15. B 트리 — 노드마다 원소 수를 범위 안에 두고 넘치면 나누면 모든 잎이 같은 깊이에 남는 이유 16. B+ 트리 — 원소는 잎에만 두고 길잡이는 경계로만 쓰면 잎 사슬 하나로 구간을 차례로 읽는 이유 Link-Cut Tree 17. 링크-컷 트리 — 트리를 수열로 펴서 스플레이 트리에 담으면 잇기 · 빼기 · 연결 묻기가 함께 상각 로그에 드는 이유 Sparse Table 18. Sparse Table — 길이가 2 의 거듭제곱인 구간을 미리 접어 두면 어느 구간이든 칸 두 개로 접히는 이유 Interval Tree 19. 구간 트리 — 노드마다 부분트리의 가장 큰 끝점을 적어 두면 겹치는 구간을 답의 수에 매인 비용으로 찾는 이유 확률·근사 자료구조 20. 블룸 필터 — 원소마다 무작위로 정한 자리 k 개를 켜 두면 넣은 원소에는 틀리지 않고 넣지 않은 원소에만 정해 둔 몫 이하로 틀리는 이유 21. 카운트-민 스케치 — 원소마다 줄 여럿의 칸 하나씩에 증분을 더하고 가장 작은 칸을 답하면 실제 빈도 아래로는 틀리지 않고 위로만 정해 둔 몫 이하로 틀리는 이유 22. HyperLogLog — 레지스터마다 첫 1 의 위치 가운데 가장 큰 값만 남기면 원소를 담지 않고도 서로 다른 원소의 수를 어림하고 따로 센 둘을 합칠 수 있는 이유 23. 뻐꾸기 필터 — 원소 대신 지문을 담고 다른 자리를 지문만으로 계산하면 원소 없이도 사본을 옮기고 지울 수 있는 이유 24. MinHash — 해시 함수마다 들어온 원소의 가장 작은 값 하나만 남기면 두 서명에서 값이 같은 칸의 몫이 자카드 닮음을 어림하는 이유 25. 스킵 리스트 — 노드마다 동전을 던져 층 수를 정하면 어떤 입력에도 찾는 길의 기댓값이 로그인 이유 26. 동시성 스킵 리스트 — 0 층 다음 칸 하나를 CAS 로 바꾸는 순간이 곧 연산이 일어난 순간인 이유 마무리 |