PBDS Hash
PBDS Hash에 관한 간단한 정리.
← 지식 노트
자료구조.
Related Contents
기록 15
최근 업데이트 순Hash
hash에서 충돌 방지 정책은 중요하다. 가장 간단하게는 이미 사용중인 영역을 만났을 때 주소값을 +1 하는 Open Addressing의 Linear Probing 방식이 대표적이지만, 여기서는 Chaining 방식의 구현을 알아보겠다. Chaining 방식의 경우 값 삭제도 원할하게
Splay Tree
Splay 연산은 해당되는 Node를 루트로 올리는 연산이다. 이를 수행하기 위해 Rotaate 함수를 만드는데, 이 함수는 해당 노드를 부모로 올리는 역할이다.
Binary Search Tree
Worst 때문에 쓸 일 없겠지만 basic 중의 basic.
Segment Tree
Point Update와 Range Query를 지원하는 가장 기본적인 SegTree이다. 메모리는 2*N 만큼 선언하면 된다.
Queue
Queue 관련 기록.
Vector
Vector 관련 기록.
BigInt
BigInt 관련 기록.
Trie
Trie 관련 기록.
2D-Fenwick Tree
2D-Fenwick Tree 관련 기록.
Fenwick Tree
Fenwick Tree 관련 기록.
PBDS Set
PBDS Set에 관한 간단한 정리. 알게 되었는데 정리 안하면 나중에 다시 맨땅에서 구글링 해야하므로 한번 알게 된 내용 정리하고 가보려고 한다.
SIMD
SIMD에 관한 간단한 정리. 알게 되었는데 정리 안하면 나중에 다시 맨땅에서 구글링 해야하므로 한번 알게 된 내용 정리하고 가보려고 한다.
Disjoint Set
MST의 크루스칼과 같은 알고리즘에서 유용하게 쓰이는 Disjoint Set에 대한 간단한 정리
Heap
Heap 관련 정리. Heap은 주로 Array로 구현하며, 가장 큰 아이템이나 가장 작은 아이템을 O(1)의 시간복잡도로 구할 수 있으며, 이를 업데이트 하는데에 O(log n)의 시간이 걸리는 자료구조이다. set 처럼 k 값을 가지는 아이템을 찾거나 할 수는 없지만, 구조가 비교적