6. 자료구조

Linked list

Linked list: 서로 떨어져 있는 데이터를 메모리 주소를 참조함으로써 이러진 것처럼 사용할 수 있다.
데이터를 담고 있는 데이터 필드와 다음 노드를 가르키는 포인터부분으로 노드가 이루어져있다.
구현 방법에 따라, single linked list와 double linked list, circular linked list 등으로 구분할 수 있다.
Array vs Linked list
- Array
  - 중간에 값을 삽입하고 싶다면, 삽입할 위치 뒤의 모든 데이터가 한 칸씩 이동해야 한다는 단점 존재
  - 메모리상 뒤쪽의 메모리가 비어있지 않으면, 모든 데이터가 더 큰 홀로 이사를 가야 한다는 단점도 존재
- Linked list
  - array의 단점을 모두 해소
  - N번째 데이터를 참조하고 싶을 때, 계속해서 다음 주소를 참조하는 형식으로 따라가야 하므로 메모리 참조에 시간이 오래 걸린다.

Linked list: 삽입과 삭제가 빈번한 경우에 사용
Array: 참조가 빈번한 경우에 사용

시간복잡도 비교

구분	Array	Linked list
insert	$O (n)$	$O (1)$
delete	$O (n)$	$O (1)$
find	$O (1)$	$O (n)$

linked list 삽입, 삭제, 접근 방법
- 접근: 원하는 원소가 나올때까지 링크 필드(포인터, 다음 노드)를 계속해서 탐색한다.
- 삽입: 삽입할 노드의 next에 현재 위치의 next를 연결한 후, 현재 위치의 next에 삽입할 노드의 주소를 넣어준다.
- 삭제: 삭제할 노드의 next를 앞선 노드의 next에 연결해준다.
Single linked list
- 가장 기본적인 구조로 되어 있으며, head에서 tail까지 단방향으로 포인터가 이어져 있으므로 N 번째 노드에서 N-1 번째 노드에 접근할 수 없다. 대신, 다시 head로부터 N-1 번의 탐색을 통해 접근해야 한다.
Double linked list
- 뒤의 노드의 주소뿐만 아니라, 이전 노드의 주소도 담고 있다. 하나의 노드는 하나의 데이터와 두 개의 링크를 가지고 있으며, 각각의 링크를 prev와 next라고 부른다. 다음 노드를 참조하고 싶다면 next 링크가 담고 있는 주소를 확인하면 되고, 이전의 노드를 참조하고 싶다면 prev 링크가 가지는 주소를 확인하면 된다.
Circular linked list
- tail이 다시 head를 가리키는 구조를 가지고 있다. 따라서, tail 노드의 next에는 NULL이 들어가는 것 대신, head의 주소가 들어간다.

Hash table

해시 테이블: (Key, Value)로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있는 자료구조이다.
빠른 검색속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다.
각각의 Key값에 해시함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용해 값을 저장하거나 검색하게 된다. 여기서 실제 값이 저장되는 장소를 버킷 또는 슬롯이라고 한다.
해시 값이 충돌하는 경우
만약 "John Smith"를 해시 함수를 돌려 나온 값과 "Sandra Dee"를 해시 함수를 돌려 나온 값이 동일하다면, 아래와 같이 해결할 수 있다.
- 해결방법 1: Separate Chaining(분리 연결법)
  - 동일한 버킷의 데이터에 대해 자료구조를 활용해 추가 메모리를 사용하여 다음 데이터의 주소를 저장하는 방법이다. 동일한 해시 값을 가지면, 동일한 버킷 안에 엔트리를 할당해줘야한다.
  - 장점
    - Chaining 방식은 해시 테이블의 확장이 필요없고 간단하게 구현이 가능하며, 손쉽게 삭제할 수 있다는 장점이 있다.
  - 단점
    - 데이터의 수가 많아지면 동일한 버킷에 chaining되는 데이터가 많아지며 그에 따라 캐시의 효율성이 감소한다는 단점이 있다.
- 해결방법 2: Open Addressing(개방주소법)
  - 추가적인 메모리를 사용하는 Chaining 방식과 다르게 비어있는 해시 테이블의 공간을 활용하는 방법이다. Open Addressing을 구현하기 위한 대표적인 방법으로는 3가지 방식이 존재한다.
    - Linear Probing: 현재의 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어 있는 버킷에 데이터를 저장한다.
    - Quadratic Probing: 해시의 저장순서 폭을 제곱으로 저장하는 방식이다. 예를 들어 처음 충돌이 발생한 경우에는 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2^2, 3^2 칸씩 옮기는 방식이다.
    - Double Hashing Probing: 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식이다. 해시된 값을 한번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 많은 연산을 하게 된다.
- 충돌 방지 방법은 데이터 클러스터링을 줄이지만 공간을 많이 사용함
- 해시 테이블이 70~80% 이상 차면 충돌이 많아져 성능이 저하됨
- 테이블 확장은 성능을 크게 떨어뜨리므로 가급적 피해야 함
- 자주 쓰이는 데이터를 캐시에 저장하면 성능 향상 가능

Stack

스택: LIFO (Last In First Out) 구조의 자료형으로 한 쪽으로만 데이터를 넣고 뺄 수 있다. push 명령으로 데이터를 넣고, pop 명령으로 가장 마지막에 들어간 데이터를 빼낸다.
브라우저의 뒤로가기 기능, ctrl + z (되돌리기), 지역 변수와 매개변수를 저장하는 stack 메모리 등에 사용된다. 이외에도 DFS 알고리즘 등 다양한 곳에 사용되는 자료형이다.
더 넣을 공간이 없는데 데이터를 push 하는 경우 overflow, 반대로 데이터가 없는데 pop 하는 경우를 underflow 라고 한다.

Queue

큐: FIFO (First In First Out) 구조의 자료형으로 출구(front)와 입구(rear or back)가 따로 존재하여 먼저 입력된 데이터가 먼저 반환된다.
push 명령으로 rear 에 자료를 넣는다. rear += 1 되어 다음에 데이터를 받을 메모리를 가리켜야 한다. pop 명령으로 front 에서 데이터를 빼낸다. front += 1 되어 다음에 데이터를 반환할 메모리를 가리켜야 한다.
CPU 연산처리 작업대기, 프린터 인쇄, 프로세스 관리 등 들어온 순서를 보장해야하는 경우 사용된다. 이외에도 BFS 알고리즘 등에 사용된다.
rear 가 기리키는 공간에 데이터가 있는데 데이터를 push 하는 경우 overflow, 반대로 front 가 가리키는 공간에 데이터가 없는데 pop 하는 경우를 underflow 라고 한다.

Circular queue

일반 Queue는 꽉 차면 rear가 마지막(N-1)을 가리켜 더 이상 추가할 수 없는 문제를 해결하기 위해 원형 큐를 사용한다.
- 처음에는 front 와 rear 가 같은 메모리를 가리킨다.
- 데이터를 입력하기 위해 rear 는 메모리가 꽉찼는지 검사한다. 꽉찬 경우는 rear 다음 번의 메모리가 front 를 가리키는 경우 (rear + 1 == front) 인데, 꽉차지 않았다면 데이터를 입력하고 rear 는 다음 메모리로 이동한다.
- 데이터를 반환하기 위해 front 는 메모리가 비었는지 검사한다. 빈 경우에는 현재 front 위치와 rear 위치가 같은 경우 (rear == front) 인데, 비지 않았다면 데이터를 반환하고 front 는 다음 메모리로 이동한다.

Graph

그래프 구현 방식
- 인접행렬: 노드를 인덱스로 삼는 2차원 배열을 만들어 각 노드가 간선으로 연결되어있으면 배열에 1을 넣어주고, 연결되지 않았다면 0을 넣어주면 된다.
  
  두 노드의 연결관계를 조회할 때, $O (1)$ 시간이 걸린다. 그러나 모든 정점에 대해, 간선 정보를 입력해야하므로 초기화에 $O (N^{2})$ 시간이 소요된다.
  노드의 수가 많고, 간선의 수가 적은 그래프의 경우에, 공간을 낭비하게 된다.
- 인접리스트: 그래프의 노드들을 리스트로 표현한다. head 노드와 연결된 노드들을 링크에 달아주면 된다.
  - 한 정점에 연결된 노드들의 정보를 얻기 위해서 $O (M)$ 시간이 걸린다.(M은 간선의 수) 간선 정보만 유지한다.
  - 공간 낭비가 적으나 두 정점이 연결되었는지 확인하기 위해서 $O (M)$ 시간이 걸리며, 구현이 비교적 어렵다.

Tree

트리: 그래프의 일종으로, 부모 노드 밑에 여러 자식 노드가 연결되고, 자식 노드 각각에 다시 자식 노드가 연결되는 재귀적 형태의 자료구조이다.
노드들은 서로 다른 자식 노드를 가지며 이때 각 노드는 재사용 되지 않는다. 트리는 다음과 같은 특징을 갖는다.
- 반드시 하나의 루트 노드만이 존재한다.
- 모든 자식 노드는 한 개의 부모 노드만을 가진다.
- 서로 다른 임의의 두 노드에 대해 두 노드를 연결하는 경로는 유일하다.
- 사이클을 가지는 노드 집합이 존재하지 않는다.
- 노드가 N개인 트리는 항상 N-1개의 간선을 가진다.
용어
- 노드(node): 트리를 구성하는 기본 원소
- 루트 노드(root node/root): 트리에서 부모가 없는 최상위 노드, 트리의 시작점
- 부모 노드(parent node): 루트 노드 방향으로 직접 연결된 노드
- 자식 노드(child node): 루트 노드 반대 방향으로 직접 연결된 노드
- 형제 노드(siblings node): 같은 부모 노드를 갖는 노드들
- 잎 노드(leaf node)/단말 노드(terminal node): 자식이 없는 노드
- 경로(path): 한 노드에서 다른 한 노드에 이르는 길 사이에 있는 노드들의 순서
- 길이(length): 출발 노드에서 도착 노드까지 거치는 노드의 개수
- 깊이(depth): 루트 경로의 길이
- 레벨(level): 루트 노드(level=1)부터 노드까지 연결된 링크 수의 합
- 높이(height): 가장 긴 루트 경로의 길이
- 차수(degree): 각 노드의 자식의 개수
- 트리의 차수(degree of tree): 트리의 최대 차수 = max[deg1, deg2, ..., degn]
- 크기(size): 노드의 개수
- 너비(width): 가장 많은 노드를 갖고 있는 레벨의 크기

Binary tree

각각의 노드가 최대 두 개의 자식 노드를 가지는 트리를 말한다. 즉, 모든 노드의 차수(degree)가 2 이하인 트리를 말한다. 이진 트리의 모든 서브 트리들은 모두 이진 트리이다.
순회 방법
- 전위 순회(preorder)
  - 순서: 루트 → 왼쪽 → 오른쪽
  1. 노드를 방문한다.
  2. 왼쪽 서브 트리를 전위 순회한다.
  3. 오른쪽 서브 트리를 전위 순회한다.
- 중위 순회(inorder)
  - 순서: 왼쪽 → 루트 → 오른쪽
  1. 왼쪽 서브 트리를 중위 순회한다.
  2. 노드를 방문한다.
  3. 오른쪽 서브 트리를 중위 순회한다.
- 후위 순회(postorder)
  - 순서: 왼쪽 → 오른쪽 → 루트
  1. 왼쪽 서브 트리를 후위 순회한다.
  2. 오른쪽 서브 트리를 후위 순회한다.
  3. 노드를 방문한다.
- 레벨 순서 순회(level-order)
  - 모든 노드를 낮은 레벨부터 차례대로 순회한다. 레벨 순서 순회는 너비 우선 순회(breadth-first traversal)라고도 한다.

완전이진트리

마지막 level을 제외한 나머지 level에 노드들이 가득 차있고, 마지막 level에서 노드는 가장 왼쪽부터 채워지는 형태의 binary tree이다.

Binary Search Tree

BST: 아래의 성징을 가지고 있는 이진트리이다.
- 각각의 모든 노드들의 값(key)은 중복된 값이 아니다.
- 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.
- 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다.
- 좌우 서브트리는 각각이 다시 이진 탐색 트리여야 한다.
탐색
- 검색하고자 하는 값을 루트 노드와 먼저 비교하고, 일치할 경우 루트 노드를 리턴한다.
  - 불일치하고 검색하고자 하는 값이 루트 노드의 값보다 작을 경우 왼쪽 서브트리에서 재귀적으로 검색한다.
  - 불일치하고 검색하고자 하는 값이 루트 노드의 값보다 큰 경우 오른쪽 서브트리에서 재귀적으로 검색한다.
삽입
- 삽입을 하기 전, 탐색을 수행한다. 트리를 탐색한 후 키와 일치하는 노드가 없으면 마지막 노드에서 키와 노드의 크기를 비교해서 왼쪽이나 오른쪽에 새로운 노드를 삽입한다.
삭제
- 삭제하려는 노드의 자식 수에 따라
  - 자식 노드가 없는 노드(리프 노드) 삭제: 해당 노드를 단순히 삭제한다.
  - 자식 노드가 1개인 노드 삭제: 해당 노드를 삭제하고 그 위치에 해당 노드의 자식 노드를 대입한다.
  - 자식 노드가 2개인 노드 삭제: 삭제하고자 하는 노드의 값을 해당 노드의 왼쪽 서브트리에서 가장 큰 값으로 변경하거나, 오른쪽 서브트리에서 가장 작은 값으로 변경한 뒤, 해당 노드(왼쪽 서브트리에서 가장 큰 값을 가지는 노드 또는 오른쪽 서브트리에서 가장 작은 값을 가지는 노드)를 삭제한다.
시간 복잡도
- BST의 탐색, 삽입, 삭제의 복잡도는 모두 O(h)이다. (h는 BST의 높이) BST는 평균 시간 복잡도가 O(log2⁡n)이지만 최악의 경우 O(n)이다.(한쪽에 치우친 트리인 경우)

Heap(binary heap)

최대값 및 최소값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진 트리를 기본으로 한 자료구조이다.
- A가 B의 부모 노드이면, A의 키값과 B의 키값 사이에는 대소관계가 성립한다.
  - heap 종류에는 min heap, max heap이 존재한다.
  - 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 루트 노드에 오게 되는 특징이 있으며, 이를 응용하여 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다.
이진 힙
- 트리를 T, 임의 내부 노드를 v라고 하면 다음과 같다.
  1. 루트 노드를 제외한 각 내부 노드는 key(T.parent(v)) < key(v) 또는 key(T.parent(v)) > key(v)이다. (즉, 키 값은 오름차순이거나 내림차순이다.)
  2. 마지막 왼쪽 결합 노드들의 레벨을 제외한 다른 모든 레벨들은 완전 이진 트리를 형성한다.
힙 리스트(heap list)로 표현할 때 i번째 노드의 왼쪽 자식 노드의 위치는 2i가 되며, i번째 노드의 오른쪽 자식 노드의 위치는 2i+1이고, 또한 i번째 노드의 부모 노드의 위치는 i/2가 된다.
이진 힙의 시간복잡도는 $O (l o g n)$ 이다.

min heap

최소 힙(min heap)은 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리이다.
$k e y (부 모 노 드) \leq k e y (자 식 노 드)$

Max heap

최대 힙(max heap)은 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리이다.
$k e y (부 모 노 드) \geq k e y (자 식 노 드)$

B Tree

이진 트리(Binary Tree)를 확장해 모든 리프 노드들이 같은 높이를 갖도록 하는 트리이다. 노드 내에 여러 개의 key가 있을 수 있으며, 최대 key의 개수에 따라 2개이면 2차 B-트리, N개면 N차 B-트리라고 부른다.
B-트리는 다음의 조건을 만족한다.
- 노드의 key의 개수가 N이면, 자식 노드의 개수는 N+1이다.
- 노드 내의 key는 오름차순으로 정렬되어 있다.
- 루트 노드는 2개 이상의 자식을 가져야 한다.
- 루트 노드를 제외한 나머지 노드들은 적어도 최대 M/2개의 key를 가져야 한다.
  - M은 B-트리의 차수를 말한다.
- 리프 노드는 모두 같은 레벨에 있어야 한다.
B+ 트리: B-트리와 비슷하지만 리프노드가 연결리스트의 형태를 띄어 선형 검색이 가능한 트리이다. 모든 노드에 key와 data가 있는 B 트리와는 달리 B+ 트리는 리프 노드에만 data가 존재한다. 또한 삽입과 제거 연산 모두 리프 노드에서만 이루어진다.