자료구조와 STL

1. 자료구조란? 데이터를 기억장치에 저장하는 방법

2. 선형구조와 비선형 구조

선형구조	스택, 큐, 데크, (선형, 연결)리스트, 배열
비선형구조	트리, 그래프

3. 순차자료구조와 연결자료구조

순차자료구조	물리적 메모리 저장주소도 순서대로 연속적으로 : 배열 사용, 배열
연결자료구조	물리적 메모리 저장주소는 순서와 상관없음 : 포인터 사용, List

 

4. 스택과 큐

스택(Stack) : Last In First Out으로 먼저 들어간 것이 나중에 나오는 구조

큐(Queue) : First In First Out으로 먼저 들어간 것이 먼저 나오는 구조

https://cdoiden.tistory.com/16?category=877084 

[기초 자료구조] 스택

STL의 경우 Stack<자료형>, Queue<자료형> 을 이용할 수 있다. 둘 모두 뒤에서 넣는 것만 가능하기 때문에 이를 보완한 Deque를 사용하는 경우도 있다. Deque는 front와 back 모두에서 데이터를 push, pop할 수 있는 queue이다. 

 

STL Container time complexity 비교, https://medium.com/@rodrigues.b.nelson/choosing-wisely-c-containers-and-big-oh-complexity-64f9bd1e7e4c

* 많은 STL 컨테이너 중에서 어떤 것을 사용해야 적절할까?

정답은 없겠지만, 구현 시 위의 표를 참고하여 가장 Time Complexity가 빠른 것을 선택하는 방법도 있을 것이다. 

list의 경우에는 최악의 경우도 삽입(Insertion)이 O(1)이라는 장점이 있다. deque와 vector는 최악의 경우 O(n)일 수도 있다(amortized). 하지만 list는 임의 index로 인한 접근이 불가능하다. set과 map의 경우에는 어떤 key를 이용하여 그 안의 value를 찾는 기능이 필요할 때 사용할 수 있을 것이다. priority_queue의 경우에는 이후의 Heap을 구현할 때, 우선순위를 이용하여 사용할 수 있을 것이다.

 

5. 트리

트리(Tree): 나무 모양의 자료구조로 1:다의 관계를 가진다. 각 노드를 탐색하는 것을 순회라고 하는데, 순회의 종류는 전위, 중위, 후위 순회가 있다. 전, 중, 후는 부모 노드를 탐색하는 순서이다.

 

- 전위 순회: 부모 - L - R

- 중위 순회: L - 부모 - R

- 후위 순회: L - R - 부모

 

* 이진 트리 분류

포화 이진 트리(Perfect Binary Tree)	모두 2개의 자식을 가지는 트리
완전 이진 트리(Complete Binary Tree)	포화 이진 트리에서 가장 아래 오른쪽 Node 부터 제거된 트리
전 이진 트리(Full Binary Tree)	모든 Node가 0 또는 2개의 자식을 가지는 트리
이진 탐색 트리(Binary Search Tree)	1. Key가 Unique 2. 왼쪽 자식이 부모보다 작음 3. 오른쪽 자식이 부도보다 큼 4. 모든 Subtree도 이진 탐색 트리

 

* Red Black Tree

위의 set과 map이 이 Tree를 가지고 구현되었다. 

 

6. Heap

완전 이진트리의 일종으로, 우선순위 큐를 이용해 만든다. 종류는 부모가 자식보다 큰 최대 힙(Max Heap), 반대의 경우인 최소 힙(Min Heap)이 존재한다. 

 

6-1) Heap 연산 (Max Heap 기준)

① 삽입

가장 마지막 인덱스에 삽입 -> 부모와 비교하여 부모보다 크면 swap, 아니면 그대로 -> 반복

 

② 삭제

root 노드 삭제 -> root 자리에 맨 마지막 노드를 가져옴 -> Heap 재구성

 

7. 그래프(Graph)

다:다로 연결되어 있는 자료구조이다. 간선과 가중치, 정점이라는 용어를 주로 사용하게 되는데, 비유를 하자면 정점은 도시, 간선은 정점을 잇는 도로, 가중치는 도로를 지나는 비용(시간적 등)이다. 그래프는 보통 경로 알고리즘에 주로 사용된다. 그래프 탐색 관련한 알고리즘으로 유명한 BFS, DFS와 최단 경로로 알려진 다익스트라, A* 등이 있다. 그래프를 만드는 방법은 리스트를 이용하는 방법과, 행렬(배열)을 이용하는 방법이 있다. 

 

그래프 알고리즘 링크(추가 예정): 

 

8. Hash

Hash는 시간 복잡도(Time Complexity)가 O(1)이라는 말을 들어본 적이 있을 것이다. 이는 가변 길이의 문자열 등을 특정 공식을 이용하여 고정 길이의 정수로 바꾸어 이를 해시 테이블의 인덱스로 사용하기 때문이다. 즉, 문자열 ABC -> 1234로 변환이 되면 1234라는 Key를 통해 Value 값을 찾는 형태이므로 이상적인 경우 O(1)이다. 하지만 ABC -> 1234이고 BCA -> 1234가 나오게 된다면 이름 충돌(collision)이라고 하며, 체이닝과 개방 주소법을 이용하여 해결한다. 

좋은 해쉬 알고리즘은 중복이 전혀 없는 것을 의미할 것이다.

*로드 팩터: 데이터의 갯수 n / 테이블의 크기 k로 나눈 값으로, 해시 테이블의 크기를 재할당하는 기준 값으로 쓰인다. 

 

8-1) 체이닝(Chaining)

해쉬값(변환된 값)이 중복되는 경우 연결 리스트를 이용하여 기존의 해쉬값 뒤에 연결{Key, Value}한다. 연결리스트를 사용하기 때문에 어떤 인덱스가 들어왔을 때 그 Value값을 확인하기 위해선 O(N)의 시간복잡도를 갖는다.

 

8-2) 개방 주소법

① 선형 프로빙

해쉬테이블에 해쉬값을 넣으려는데 이미 슬롯이 차있다면 다음 슬롯으로 한 칸씩(선형) 옮겨서 넣는 방식이다.

 

② 이차 프로빙

선형 프로빙에서 선형 대신에 2차함수의 값을 이용해 빈 슬롯을 찾아다니는 형태인데, 2차 함수의 출력 값이 입력에 따라 고정이므로 입력에서 중복이면 그 뒤에도 계속 이전 값과 충돌이 일어날 수 있다.

 

③ 이중 해싱

두 개의 해시 함수(이중 해싱)와 모듈러 연산을 이용하여 빈 슬롯을 찾아다니는 형태이다.

 

9. Map

Key와 Value로 값을 저장하는 형태로, 어떤 Key를 가지고 있으면 Map에서 Value를 꺼내 쓸 수 있는 형태이다. 이를 위해 Key가 중복되지 않아야한다.

 

* STL map과 unordered_map

unordered_map은 해쉬맵(HashMap)을 이용한 자료구조로 map보다 빠른 속도를 갖는다. 이름과 같이 값에 따라 정렬되지는 않는다. 정렬되는 자료구조는 Tree를 이용한 TreeMap이다.

 

* Set과 Map

Set은 Map에서 Value도 중복되지 않는 자료구조이다.

 

* HashMap과 HashTable

HashMap은 key와 value에 null값이 들어갈 수 있고 동기화를 보장하지 않는다. HashTable은 key와 value에 null값이 들어가지 못하며 동기화를 보장한다.