Data Structure 0. 자료구조
0. 자료구조
1. 정의
자료구조(Data Structure)는 자료의 관리와 저장을 다루는 학문의 분야이다. 프로그래밍에서는 데이터를 효율적으로 관리하고 탐색하는 데 어떤 형태의 자료구조를 사용하는지에 따라 효율성이 매우 달라지므로 적절한 자료구조를 사용하는 역량이 필수적이다.
효과적으로 설계된 자료구조는 메모리 용량의 관리에 탁월하며, 게임에 있어서는 렉 유발 등을 줄이는 데 효과적이다.
알고리즘의 효율성은 빅오 표기법을 따른다. 빅오 표기법의 수학적 정의는 다음과 같다:
모든 $n \geq n_0 \gt 0$ 에 대하여 $0 \leq f(n) \leq kg(n)$ 인 양의 상수 $k$ 와 $n_0$ 가 존재하면 $f(n) = O(g(n))$ 이다.
이러한 표기법은 알고리즘의 시간 복잡도를 나타내게 된다. 간단히 말하면 최악의 경우를 상정하여 계산하는 것으로, 시간 복잡도로 알고리즘의 연산 효율성을 대략적으로 구분할 수 있다.
예를 들어, $O(1)$은 데이터 개수에 영향을 받지 않는 상수 시간복잡도를 가진다는 뜻이며, $O(n)$은 데이터 개수 n에 비례하여 연산량 및 소요 시간이 증가한다는 의미이다.
2. 종류
자료구조는 자료의 특성에 따라 혹은 구현 방식에 따라 여러 분류가 있으며, C++ 에는 이를 프로그래머가 직접 구현하지 않아도 쉽게 사용 가능하도록 표준 탬플릿 라이브러리(STL)로써 제공한다.
- 배열(Array)
- 스택(Stack)
- 큐 (Queue)
- 덱 (Deque)
- 연결 리스트(Linked list)
- 단일 연결 리스트
- 이중 연결 리스트
- 트리(Tree)
- 이진 트리(Binary tree)
- 힙(Heap)
- 이진 트리(Binary tree)
- 해시 테이블(Hash table)