Related to: Data Structures
개요
자료구조는 데이터를 저장하고 조직화하는 방식으로, 효율적인 접근, 수정, 탐색, 삭제를 가능하게 합니다. 적절한 자료구조의 선택은 알고리즘의 성능에 직접적인 영향을 미칩니다.
핵심 개념
분류 기준
- 선형 구조 데이터가 순차적으로 나열됨 → 배열(Array), 연결 리스트(Linked List), 스택(Stack), 큐(Queue)
- 비선형 구조 데이터가 계층적 또는 관계적으로 구성됨 → 트리(Tree), 그래프(Graph), 힙(Heap), 트라이(Trie)
주요 자료구조
- 배열 (Array)
고정 크기의 연속된 메모리 공간에 저장
- 장점: 인덱스 기반 접근 O(1)
- 단점: 삽입/삭제 시 비용 O(n)
- 연결 리스트 (Linked List)
각 노드가 데이터와 다음 노드를 참조
- 단일, 이중, 원형 형태 존재
- 삽입/삭제 O(1), 검색 O(n)
- 스택 (Stack)
후입선출(LIFO) 구조
- 사용 예: 함수 호출 스택, 괄호 검사
- 큐 (Queue)
선입선출(FIFO) 구조
- 변형: 덱(Deque), 우선순위 큐(Priority Queue)
- 힙 (Heap)
완전 이진트리 기반의 우선순위 큐 구현
- 최대 힙: 부모 ≥ 자식
- 최소 힙: 부모 ≤ 자식
- 트리 (Tree)
계층적 구조 (부모-자식 관계)
- 이진 탐색 트리(BST), AVL, Red-Black Tree, B-Tree
- 그래프 (Graph)
정점(Vertex)과 간선(Edge)으로 표현되는 일반적인 관계 구조
- 방향성, 가중치 여부에 따라 다양한 종류 존재
자료구조 선택 기준
자료구조와 알고리즘의 관계
자료구조는 알고리즘의 기반 인프라로 작동합니다. 예: 이진 탐색은 정렬된 배열 또는 이진 탐색 트리에서만 유효함.
관련 개념
- Tree — 계층적 구조의 비선형 자료구조
- Graph — 정점과 간선으로 구성된 자료구조
- Heap — 완전 이진트리 기반 우선순위 큐
- Binary Tree란 무엇일까 — 이진 트리의 종류와 특성
- 그래프와 트리(Tree and Graph) — 그래프와 트리의 비교
- Algorithm — 자료구조를 활용하는 알고리즘
- Decision Tree — 머신러닝에서의 결정 트리