서로소 집합(Disjoint-Set)
서로소 집합(Disjoint-Set)은 집합, 혹은 그룹을 관리하는 효율적인 알고리즘입니다. 각각의 그룹을 트리 구조로 관리하는 이 알고리즘은 크게 두 가지의 연산을 가집니다. find(x): x번 노드의 최고 조상(루트)을 찾는…
2024-05-254분
Category: Data Structures
10← All postsBinary Indexed Tree
Binary Indexed Tree(또는 fenwick tree, 이하 BIT)는 Segment Tree와 비슷하게 구간에 대한 정보를 저장할 수 있는 자료구조입니다. 기본적으로 아래의 그림과 같은 1-based 구조를 가지며,…
2024-05-242분
세그먼트 트리(Segment Tree)
세그먼트 트리(Segment Tree)는 구간에 대한 정보를 빠르게 구해낼 수 있으며 완전 이진트리 형식의 구조를 가지는 자료구조입니다. 구간 최소값을 구하는 세그먼트 트리 예시 구간의 최솟값을 구하는 세그먼트 트리는 먼저 구하고자…
2024-05-234분
Hashing (해싱)
해싱은 임의의 길이의 데이터(키, Key)를 고정된 길이의 데이터(해시값, Hash value)로 변환해 작은 크기의 해시 테이블로 대응(Mapping)시켜 식별하는 하나의 기법입니다. 해시 테이블은 M개의 버킷으로 이루어져…
2024-05-093분
힙 (Heap)
힙 heap 은 최댓값 또는 최솟값을 빠르게 찾아낼 수 있는 트리형 자료구조입니다. 힙은 완전이진트리 형식을 따르며 모든 부모 노드의 값이 자식 노드들의 값과 일정한 대소 관계를 가지게 되는 규칙을 가지고 있습니다.
2024-05-083분
Tree (트리)
트리는 자식과 부모의 관계로 이루어진 계층적인 구조입니다. 필요에 따라 다양한 종류로 나뉘게 되는데 이번에는 제일 간단한 트리인 이진 트리에 대해서 설명하려고 합니다. 먼저 이진 트리에서 사용하는 용어들을 정리해보면 다음과…
2024-05-077분
Stack(스택)
스택은 선형 구조이며, 마지막으로 삽입된 값이 가장 먼저 나오는 LIFO(Last in First Out)으로 되어 있습니다. 이 때 삽입하는 과정을 push라고 하며 값을 빼내는 과정을 pop이라고 합니다. 예를 들면 a, b,…
2024-05-062분
Queue (큐)
큐는 선형 구조이며, 삽입된 순서대로 값이 나오는 FIFO(First in First Out)로 되어 있습니다. 이때 삽입하는 과정을 enqueue라고 하며 값을 빼내는 과정을 dequeue라고 합니다. 예를 들면 a, b, c…
2024-05-054분
List(연결리스트)
연결리스트는 랜덤 접근이 가능한 배열과는 다른 순차적인(sequential) 자료구조입니다. 연결리스트는 노드들로 구성되어 있습니다. 노드는 저장할 값과 다음 노드를 가리키는 포인터로 이루어져 있습니다. 연결리스트의 첫 노드인…
2024-05-032분
Graph (그래프)
그래프란 어떤 상태 혹은 객체 간의 관계를 나타내는 자료구조입니다. 그래프는 정점(Vertex)과 간선(Edge)으로 구성됩니다. 정점이란 어떠한 상태 혹은 객체를 나타냅니다. 간선은 그러한 정점 간의 관계, 그중에서도 연결성을…
2024-05-024분