1.
Tree: 컴퓨터 과학에서 매우 중요한 자료구조입니다. 이진 트리, AVL 트리, 붉은-검은 트리, B-트리, 트라이(Trie), 세그먼트 트리 등 다양한 트리 자료구조가 존재하며, 이들은 그래프, 데이터베이스, 머신러닝 등 여러 분야에서 활용됩니다.
2.
Heap: Heap은 효율적인 우선순위 큐 구현에 사용되며, 다익스트라와 같은 알고리즘에서 이용됩니다. 또한, 힙 정렬 알고리즘의 기반이기도 합니다.
3.
Graph: 그래프는 노드와 이들을 연결하는 간선으로 이루어진 자료구조로, 네트워크 라우팅, 소셜 네트워크 분석 등에 널리 사용됩니다. 그래프는 방향성이 있거나 없을 수 있으며, 가중치를 가질 수도 있습니다. 그래프는 인접 리스트 또는 인접 행렬로 표현할 수 있습니다.
4.
Hash Table: 해시 테이블은 키를 값에 매핑하는 자료구조로, 데이터의 검색, 삽입, 삭제를 평균적으로 O(1)의 시간복잡도로 수행할 수 있습니다. 이는 알고리즘의 성능을 크게 향상시키는 데 도움이 됩니다.
5.
Disjoint Set/Union-Find: 이 자료구조는 여러 개의 서로 겹치지 않는 집합들에 대한 정보를 효과적으로 관리할 수 있습니다. 이는 크루스칼의 최소 신장 트리 알고리즘 등에서 활용됩니다.
6.
Trie (Prefix Tree): 문자열을 저장하고 검색하는데 효율적인 자료구조입니다. 이는 자동완성, 스펠링 체크, IP 라우팅 등에 사용됩니다.
7.
Segment Tree / Fenwick Tree (Binary Indexed Tree): 구간 쿼리 문제를 효율적으로 해결하는 자료구조입니다. 배열의 특정 구간에 대한 정보를 빠르게 업데이트하고 조회할 수 있습니다.
1.
이중 우선순위 큐 (Double-Ended Priority Queue): 이 자료구조는 가장 작은 원소와 가장 큰 원소를 모두 효율적으로 찾아낼 수 있는 우선순위 큐입니다. 힙과 같은 자료구조를 이용하여 구현할 수 있습니다.
2.
스택 (Stack): 스택은 한쪽 끝에서만 항목을 추가하거나 제거할 수 있는 자료구조입니다. 이를 통해 후입선출 (LIFO, Last In First Out) 방식의 동작을 구현할 수 있습니다.
3.
블룸 필터 (Bloom Filter): 블룸 필터는 원소의 존재 여부만을 빠르게 테스트할 수 있는 확률적 자료구조입니다. 해시 함수를 사용하여 공간 효율성을 높입니다. 원소가 존재하지 않는 것은 100% 보장하지만, 원소가 존재한다는 정보는 오차를 포함할 수 있습니다.
4.
LRU 캐시 (Least Recently Used Cache): LRU 캐시는 최근에 가장 적게 사용된 항목을 제거하는 방식으로 캐시 교체를 수행하는 자료구조입니다.
5.
스플레이 트리 (Splay Tree): 스플레이 트리는 접근된 노드를 루트로 이동하는 자기조정 이진 검색 트리입니다. 이는 일정한 패턴으로 요소에 접근하는 경우 효율적입니다.
6.
카운트-미노 (Count-Min Sketch): 카운트-미노 스케치는 데이터 스트림에서 빈도나 중량의 추정을 위한 확률적 자료구조입니다.
