[자료구조] 여러 자료구조들

◆ 자료구조란?

자료구조란 데이터를 표현하고 저장하는 방식이다.

자료구조는 다음과 같이 분류할 수 있다.

◎ 선형 자료구조

• 배열
• 연결리스트
• 스택
• 큐

◎ 비선형 구조

• 트리
• 힙
• 그래프

 

◆ 목적

자료를 더 효율적으로 저장하고, 관리하기 위해 사용한다.

잘 선택된 자료구조는 실행시간을 단축시켜 주거나 메모리 용량의 절약을 이끌어 낼 수 있다.

---

◇ 리스트List (배열Array, 연결리스트Linked List)

리스트는 선형적으로 값을 가지고 있는 자료구조이며, 보통 ①배열(Array)과 ②연결리스트(Linked List)로 나뉜다.

그중 배열은 같은 자료형의 요소들이 순서를 갖고 나열되어 있는 집합으로 메모리에 연속적으로 저장되며, 논리적 저장 순서와 물리적 저장 순서가 일치한다.

연결리스트는 메모리의 동적할당을 기반으로 각 데이터들을 포인터로 연결하여 관리하는 자료구조다. 각각의 데이터는 노드(node)로 이루어져 있으며, 각 노드들은 ①값과 ②다음 노드를 가리키는 포인터로 구성되어 있다.

 

※ 특징 및 차이점

• 배열은 인덱스로 해당 원소에 접근할 수 있다. = random access  |  하지만 연결리스트는 random access가 불가능 하다. 따라서 데이터 조회는 배열이 연결리스트보다 빠르다.
• 배열은 크기가 고정되어 있어 미리 할당을 받아야 하며 바꿀 수 없다. 반면에 연결리스트는 크기가 동적이다. 그래서 나중에 크기를 변경할 수 있는 가변 배열 자료구조도 있다. 대표적으로 C++의 vector와 Java의 ArrayList
• 배열은 삽입/삭제하는데 O(N)의 시간이 걸린다. 삽입 전/삭제 후에 데이터를 이동시켜야 하기 때문이다. 반면 연결리스트는 O(1)만에 가능하다. 그래서 삽입/삭제는 연결리스트가 더 빠르다.

---

◇ 스택 (Stack)

나중에 들어간 것이 먼저 나오는 LIFO(Last In First Out, 후입선출) 형태의 선형 자료구조

 

※ 용도

- 함수의 콜스택

- 문자열 역순 출력

- 연산자 후위표기법

---

◇ 큐 (Queue)

먼저 들어간 것이 먼저 나오는 FIFO(First In First Out, 선입선출) 형태의 선형 자료구조

 

※ 용도

- 버퍼

- BFS

---

◇ 덱 (Deque)

데이터의 입력과 출력이 양쪽 끝에서 가능한 자료구조로, 스택과 큐에 비해 자유도가 높다.

• 스크롤(scroll) : 입력이 한쪽 끝으로만 가능하도록 제한한 덱
• 셀프(shelf) : 출력이 한쪽 끝으로만 가능하도록 제한한 덱

 

그러나 실제로 양쪽의 입력과 출력을 모두 사용하는 경우는 잘 없다.

보통 두가지 이유중 하나로 사용하게 된다.

• 큐를 구현했는데 양쪽에서 출력할 수 있어야 하거나
• 스택을 구현했는데 양쪽에서 입력하고 싶은 경우

 

※ 용도

- 스케줄링

- 우선순위 조절

---

◇ 그래프 (Graph)

정점(vertex)과 간선(edge)의 집합이다.

간선은 두 정점을 이어주는 역할을 하며, 자기자신을 이을 수도 있고, 간선에 방향이 있기도 하고 없기도 하며, 가중치가 있기도 하고 없기도 하는 등 아주 다양한 형태의 그래프가 있다.

크게 무방향 그래프와 방향 그래프로 나뉘며, 연결관계를 배열과 인접리스트로 표현할 수 있다.

• 차수(degree) : 정점과 이어진 간선의 개수
• 싸이클(cycle) : 간선을 따라가다 보니 시작한 정점으로 돌아오는 경로

 

그래프의 순회 방식에는 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)가 있다.

---

◇ 트리 (Tree)

계층적 관계를 표현하는 비선형 자료구조다.

그래프의 하위집합으로 다음과 같은 특징을 가지고 있다.

1. 연결그래프다. = 컴포넌트가 하나다.
2. 방향을 무시하였을 때, 사이클(cycle)이 존재하지 않는다.
3. 트리의 간선 개수는 정점 개수보다 반드시 1개 작다. (1,2번 조건을 만족하면 자연스럽게 생기는 성질)

 

※ 용어

• 루트 노드(root) : 가장 상위의 노드
• 깊이(depth) 또는 레벨(level) : 루트 노드와의 거리
• 높이(height) : 가장 깊은 정점의 깊이 또는 그에 1을 더한 값
• 부모 노드(parent) : 서로 인접해 있는 두 정점이 있을 때, 깊이가 작은 쪽
• 자식 노드(child) : 서로 인접해 있는 두 정점이 있을 때, 깊이가 큰 쪽
• 리프 노드(leaf node) : 자식이 하나도 없는 노드
• 차수(degree) : 자식 노드의 수
• 서브 트리(subtree) : 부분 트리. 트리 속에 포함되어 있는 또 다른 트리

 

※ 순회 방식

• 전위 순회 (Preorder) : 루트 - 왼쪽 서브트리 - 오른쪽 서브트리 순으로 순회
• 중위 순회 (Inorder) : 왼쪽 서브트리 - 루트 - 오른쪽 서브트리 순으로 순회
• 후위 순회 (Postorder) : 왼쪽 서브트리 - 오른쪽 서브트리 - 루트 순으로 순회
• 레벨 순회 (level-order) : 깊이가 작은 것부터 순회. 그래프에서의 BFS와 같다.

---

◇ 이진 검색 트리 (Binary Search Tree)

이진트리 기반의 탐색을 위한 자료구조

이진 탐색 : 탐색에 소요되는 시간복잡도는 O(logN)이나 삽입, 삭제가 불가능하다.

연결리스트 : 삽입, 삭제의 시간복잡도는 O(1)이나, 탐색하는데 걸리는 시간복잡도가 O(N)이다.

둘의 장점을 합한것이 BST다. 즉, 효율적인 탐색이 가능하면서도, 삽입, 삭제가 가능한 자료구조.

 

※ 규칙

• 각 노드의 자식은 2개 이하다. (이진트리 : 각각의 노드가 최대 두개의 자식을 가지는 트리)
• 각 노드의 왼쪽 자식의 값은 부모보다 작아야 하고, 오른쪽 자식의 값은 부모보다 크다.
• 중복된 노드가 없어야 한다. = 모든 노드는 유일하다.
  • 중복이 없어야 하는 이유 : 검색이 목적인 자료구조인데 굳이 중복된 값을 넣어서 검색 속도를 느리게 할 필요가 없다. 트리에 삽입하는 것보다 노드에 count 값을 가지게 해 처리하는게 훨씬 효율적이다.

 

이진탐색트리의 순회는 '중위순회(inorder)' 방식

 

※ 시간복잡도

• 균등 트리 : O(logN)
• 편향 트리 : O(N)

시간복잡도는 정확히는 O(h)다.

편향된 트리는 시간복잡도가 O(N)이므로 트리를 사용할 이유가 사라진다. 이를 개선한 트리가  AVL Tree ,  Red Black Tree 다.

---

◇ 힙(Heap) ≒ 우선순위 큐(Priority Queue)

힙은 완전 이진 트리의 일종으로, 우선순위 큐를 위해 만들어진 자료구조다.

우선순위 큐란, 우선순위의 개념을 큐에 두고 만든 자료구조로, 데이터들이 우선순위를 가지고 있고, 높은 우선순위를 가진 데이터가 먼저 나간다.

예) 최대 힙 : 항상 최대값이 먼저 나간다.

우선순위 큐는 배열, 연결리스트, 힙으로 구현 가능하다. (힙이 가장 효율적이다!)

 

※ 용도

- 시뮬레이션

- 작업 스케쥴링

- 수치해석 계산

---

◇ 해시 테이블 (Hash Table)

해시 테이블은 연관배열  구조를 이용하여 키(Key)와 값(Value)을 저장하는 자료구조다.

 

※ 연관배열이란

키(key) 1개와 값(value) 1개가 1:1로 연관되어 있는 자료구조다. 키(key)를 이용하여 값(value)을 도출할 수 있다.

 

※ 해시 테이블의 구조

해시테이블은 키(Key), 해시함수(Hash Function), 해시(Hash), 값(value), 저장소(Bucket, Slot)로 이루어져 있다.

키(key)는 해시함수(hash function)를 통해 해시(hash)로 변경이 되며 해시는 값(value)과 매칭되어 저장소에 저장이 된다.

• 키(Key) : 고유한 값이며, 해시함수의 input이 된다. 해시 함수로 값을 바꾸어 저장한다.
• 해시함수(Hash Function) : 키(key)를 해시(hash)로 바꿔주는 역할을 한다. 다양한 길이를 가지는 키를 일정한 길이를 가지는 키로 변경하여 저장소를 효율적으로 운영할 수 있도록 도와준다. 다만, 해시 충돌이 일어날 확률을 최대한 줄이는 함수를 만들어야 한다.
• 해시(Hash) : 해시 함수의 결과물이며, 저장소에 값과 매칭이 되어 저장이 된다.
• 값(Value) : 저장소에 최종적으로 저장이 되는 값으로 키와 매칭되어 저장, 검색, 삭제, 접근이 가능하다.

 

※ 해시 충돌 (Hash Collision)

서로 다른 키(key)가 같은 해시(hash)가 되는 경우

해결방법에는

1. Chaining(체이닝) : 연결리스트로 노드를 계속 추가해나가는 방식
2. Open Addressing(개방주소법) : 해시 충돌이 일어나면 다른 버켓에 데이터를 삽입하는 방식

이 있다.