자료 구조
자료 구조
자료 구조(data structure)는 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합을 말한다.
복잡도
복잡도는 시간 복잡도와 공간 복잠도로 나뉜다.
시간 복잡도
시간 복잡도란 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계를 가리킨다. 어떠한 알고리즘의 로직이 얼마나 오랜 시간 걸리는지를 나타내는 데 쓰이며, 보통 빅오 표기법으로 나타낸다.
시간 복잡도는 왜 필요할까?
효율적인 코드로 개선하는 데 쓰이는 척도가 되기 때문이다.
입력 크기가 커질수록 차이가 많이 나기 때문에 O($n^2$)보다는 O(n), O(n)보다는 O(1)을 지향해야 한다.
자료 구조를 쓸 때 시간 복잡도
보통 시간 복잡도를 생각할 때 평균, 그리고 최악의 시간 복잡도를 고려하면서 쓴다.
자료 구조의 평균 시간 복잡도
| 자료 구조 | 접근 | 탐색 | 삽입 | 삭제 |
|---|---|---|---|---|
| 배열(array) | O(1) | O(n) | O(n) | O(n) |
| 스택(stack) | O(n) | O(n) | O(1) | O(1) |
| 큐(queue) | O(n) | O(n) | O(1) | O(1) |
| 이중 연결 리스트(doubly linked list) | O(n) | O(n) | O(1) | O(1) |
| 해시 테이블(hash table) | O(1) | O(1) | O(1) | O(1) |
| 이진 탐색 트리(BST) | O(logn) | O(logn) | O(logn) | O(logn) |
| AVL 트리 | O(logn) | O(logn) | O(logn) | O(logn) |
| 레드 블랙 트리 | O(logn) | O(logn) | O(logn) | O(logn) |
자료 구조 최악의 시간 복잡도
| 자료 구조 | 접근 | 탐색 | 삽입 | 삭제 |
|---|---|---|---|---|
| 배열(array) | O(1) | O(n) | O(n) | O(n) |
| 스택(stack) | O(n) | O(n) | O(1) | O(1) |
| 큐(queue) | O(n) | O(n) | O(1) | O(1) |
| 이중 연결 리스트(doubly linked list) | O(n) | O(n) | O(1) | O(1) |
| 해시 테이블(hash table) | O(n) | O(n) | O(n) | O(n) |
| 이진 탐색 트리(BST) | O(n) | O(n) | O(n) | O(n) |
| AVL 트리 | O(logn) | O(logn) | O(logn) | O(logn) |
| 레드 블랙 트리 | O(logn) | O(logn) | O(logn) | O(logn) |
공간 복잡도
공간 복잡도는 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양을 말한다. 정적 변수로 선언된 것 말고도 동적으로 재귀적인 함수로 인해 공간을 계속해서 필요로 할 경우도 포함한다.
선형 자료 구조
선형 자료 구조란 요소가 일렬로 나열되어 있는 자료 구조를 말한다.
- 연결 리스트
- 배열
- 벡터
- 스택
- 큐
연결 리스트
연결 리스트는 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화 시킨 자료 구조이다. 삽입과 삭제에 O(1), 탐색은 O(n)이 걸린다. 랜덤 접근이 불가능하여 순차적 접근만 가능하다.
- 싱글 연결 리스트 : next 포인터만 가진다.
- 이중 연결 리스트 : next 포인터와 prev 포인터를 가진다.
- 원형 이중 연결 리스트 : 이중 연결 리스트와 같지만 마지막 노드의 next 포인터가 헤드 노드를 가리키는 것을 말한다.
배열
배열은 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합이다. 또한, 중복을 허용하고 순서가 있다. 배열은 인덱스에 해당하는 원소를 빠르게 접근해야 하거나 간단하게 데이터를 쌓고 싶을 때 사용한다.
정적 배열을 기반으로 탐색은 O(1)이 되어 랜덤 접근이 가능하며 삽입과 삭제에는 O(n)이 걸린다.
따라서 데이터 추가와 삭제를 많이 하는 것은 연결 리스트, 탐색을 많이 하는 것은 배열로 하는 것이 좋다.
벡터
벡터는 동적으로 요소를 할당할 수 있는 동적 배열이다. 컴파일 시점에 개수를 모른다면 벡터를 사용해야 한다. 중복을 허용하고 순서가 있으며 랜덤 접근이 가능하다. 탐색과 맨 뒤의 요소를 삭제하거나 삽입하는데 O(1)이지만 맨 뒤나 맨 앞이 아닌 요소를 삭제하고 삽입하는데 O(n)이 걸린다.
스택
스택은 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 LIFO를 가진 자료 구조이다. 재귀적인 함수, 알고리즘에 사용되며 웹 브라우저 방문 기록 등에 쓰인다. 삽입 및 삭제에 O(1), 탐색에 O(n)이 걸린다.
큐
큐는 먼저 집어 넣은 데이터가 먼저 나오는 성질 FIFO를 지닌 자료 구조이며, 삽입 및 삭제에 O(1), 탐색에 O(n)이 걸린다.
CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, 너비 우선 탐색, 캐시 등에 사용된다.
비선형 자료 구조
비선형 자료 구조란 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 말한다.
- 그래프
- 트리
- 힙
- 우선 순위 큐
- 맵
- 셋
- 해시 테이블
그래프
그래프는 정점과 간서으로 이루어진 자료 구조를 말한다.
어떠한 곳에서 어떠한 곳으로 무언가를 통해 간다고 가정할 때,
- 정점 : 어떠한 곳
- 간선 : 무언가
가중치는 간선과 정점 사이에 드는 비용을 말한다.
트리
그래프 중 하나이다. 그래프의 특징처럼 정점과 간선으로 이루어져 있고, 트리 구조로 배열된 일종의 계층적 데이터 집합이다. 루트 노드, 내부 노드, 리프 노드 등으로 구성되며 트리로 이루어진 집합을 숲이라고 한다.
- 루트 노드 : 가장 위에 있는 노드를 뜻한다.
- 리프 노드 : 자식 노드가 없는 노드를 뜻한다.
이진 트리
자식의 노드 수가 두 개 이하인 트리를 의미한다.
- 정이진 트리 : 자식 노드가 0 또는 두 개인 이진 트리
- 완전 이진 트리 : 왼쪽부터 채워져 있는 이진 트리를 의미한다. 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 경우 왼쪽부터 채워져 있다.
- 변질 이진 트리 : 자식 노드가 하나 밖에 없는 이진 트리
- 포화 이진 트리 : 모든 노드가 꽉 차 있는 이진 트리
- 균형 이진 트리 : 왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진 트리, map, set을 구성하는 레드 블랙 트리는 여기에 속한다.
이진 탐색 트리
이진 탐색 트리(BST)는 노드의 오른쪽 하위 트리에는 노드 값보다 큰 값이 있는 노드만 포함되고 왼쪽 하위 트리에는 노드 값보다 작은 값이 들어 있는 트리를 말한다.
힙
완전 이진 트리 기반의 자료구조이다. 최소힙과 최대 힙 두가지가 있고 해당 힙에 따라 특정한 특징을 지킨 트리를 말한다.
- 최대힙 : 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야 한다. 또한 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 한다.
- 최소힙 : 최소힙에서 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 최솟값이어야 한다. 또한, 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 한다.
댓글남기기