자료구조(data structrue)는 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합을 이야기함.
5.1 복잡도
복잡도는 시간 복잡도와 공간 복잡도로 나뉨.
5.1.1 시간 복잡도
시간 복잡도란 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계를 의미함.
시간 복잡도의 존재 이유는 효율적인 코드로 개선하는 데 쓰이는 척도가 되기 때문임.
빅오 표기법
'가장 많이 영향을 많이 끼치는' 항의 상수 인자를 빼고 나머지 항을 없앤 것임.
5.1.2 공간 복잡도
공간 복잡도란 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양을 말함.
정적 변수 뿐 만 아니라 동적으로 재귀적인 함수로 인해 공간을 계속 해서 필요오 할 경우도 포함임.
5.1.3 자료 구조에서의 시간 복잡도
자료구조 평균 시간 복잡도
| 자료구조 | 접근 | 탐색 | 삽입 | 삭제 |
|---|---|---|---|---|
| 배열(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) |
5.2 선형 자료 구조
선형 자료 구조란 요소가 일렬로 나열되어 있는 자료구조를 의미함.
5.2.1 연결 리스트
연결리스트는 데이터를 감싼 노드를 포인터로 연결해서 공간적인 효율성을 극대화 시킨 자료구조임.
삽입과 삭제가 O(1)이 걸리며 탐색에는 O(n)이 걸림.
prev 포인터와 next포인터로 앞과 뒤의 노드를 연결시킨 것이 연결리스트임.
연결리스트는 싱글 연결 리스트, 이중 연결 리스트, 원형 이중 연결리스트가 있음.
- 싱글 연결 리스트: next 포인터만 가짐
- 이중 연결 리스트: next 포인터와 prev 포인터를 가짐
- 원형 이중 연결 리스트: 이중 연결 리스트와 같지만 마지막 노드의 next 포인터가 헤드 노드를 가리키는 것을 말함.
5.2.2 배열
배열은 같은 타입의 변수들로 이루어져 있고, 크기가 정해져 있으며, 인접한 메모리 위치에 있는 데이터를 모아놓은 집합임. 중복을 허용하고 순서가 있음.
탐색에 O(1)이 걸리기 때문에 랜덤 접근(random access)가 가능함.
랜덤 접근과 순차적 접근
랜덤 접근은 동일한 시간에 배열과 같은 순차적인 데이터가 있을 때 임의의 인덱스에 해당하는 데이터에 접근할 수 있는 기능임. 이를 직접 접근이라고도 함. 이는 데이터를 저장된 순서대로 검색해야 하는 순차적 접근과는 반대임.
배열과 연결리스트 비교
- 배열은 랜덤 접근이 가능하고, 연결 리스트는 불가능함.
- 배열은 데이터 추가가 느리지만, 연결리스트는 빠름.
5.2.3 벡터
벡터(vertor)는 동적으로 요소를 할당할 수 있는 동적 배열임. 컴파일 시점에 개수를 모른다면 벡터를 써야함. 중복을 허용하고 순서가 있고 랜덤 접근이 가능함. 탐색과 맨 뒤의 요소를 삭제하거나 삽입하는 데 O(1)이 걸리며, 맨 뒤나 맨 앞이 아닌 요소를 삭제하고 삽입하는 데 O(n)의 시간이 걸림.
벡터는 push_back()을 한다고 해서 매번 크기가 증가하는 것이 아니라, 2의 제곱승 + 1 마다 크기를 2배로 늘림.
메서드는 push_back(), pop_back(), erase(), find(), clear() 가 있음.
5.2.4 스택
스택은 가장 마지막으로 들어간 데이터가 가장 첫 번째로 나오는 성질(LIFO, Last In First Out)을 가진 자료 구조임. 재귀적인 함수, 알고리즘에 사용되며 웹 브라우저 방문 기록 등에 쓰임. 삽입 및 삭제에 O(1), 탐색에 O(n)이 소요됨.
5.2.5 큐
큐(queue)는 먼저 집어넣은 데이터가 먼저 나오는 성질(FIFO, First In First Out)을 지닌 자료 구조이며, 나중에 집어넣은 데이터가 먼저 나오는 스택과는 반대되는 개념을 가짐. 삽입 및 삭제에 O(1), 탐색에 O(n)이 걸림. CPU 작업을 기다리는 프로세스, 스레드 행렬 또는 네트워크 접속을 기다리는 행렬, 너비 우선 탐색, 캐시 등에 사용됨.
