[자료구조2] Map, Set, Priority Queue 개념 정리
자료구조 중 Map, Set, Priority Queue에 대한 개념 정리를 담고 있습니다. MapKey–Value 쌍을 저장하고 Key로 매우 빠르게 값을 찾는 자료구조.내부 원리Hash 기반(Map, HashMap, unordered_map)hash(key) -> bucket 인덱스로 가서 저장/탐색.충돌은 체이닝(연결리스트/트리) 또는 오픈어드레싱으로 해결.평균 O(1), 최악 충돌 쌓이면 O(n) (자바8은 체이닝이 트리로 바뀌어 최악 O(log n)).Tree 기반(TreeMap, std::map)균형 이진 탐색 트리(Red-Black)에 (key, value)를 정렬 상태로 저장.항상 O(log n) 탐색/삽입/삭제.정렬/범위 쿼리(lower_bound, subMap) 가능.핵심 연산 & 복..
2025. 8. 11.