Data Structure - 개념 정리(summary)

- 이전 포스팅까지 기본적인 자료구조를 공부했습니다. 이를 기반으로, 알고리즘을 공부해 나갈 계획입니다. 

- 이번 포스팅은 복습 겸 앞선 포스팅에서 다뤘던 기본적인 자료구조에 대한 개념을 정리하는 포스팅입니다.

---

1. 자료구조와 알고리즘이란? 

- 자료구조(data structure): 대량의 데이터를 효율적으로 관리하기 위해 사용하는 데이터의 저장방식을 의미한다. 저장할 데이터의 특성과 데이터 사용의 목적에 따라 해당 데이터를 저장하는 방식이 달라진다. 

 

- 알고리즘(algorithm): 프로그래밍에서 어떠한 문제를 해결하거나 풀어내기 위한 방법 또는 과정을 의미한다. 수학처럼, 한가지 문제에도 다양한 알고리즘이 존재한다. 다만, 좋은 알고리즘이란 프로그래밍 상에서 가장 적은 자원(저장공간, 메모리)을 사용하면서 가장 빠르게 연산되는 알고리즘을 의미한다.

 

즉, 올바른 자료구조와 알고리즘의 조합이 프로그램의 성능을 좌우한다. 

---

2.  Array(배열)

- 같은 종류의 데이터를 순차적으로 저장하는 자료구조

- 각 데이터마다 index가 부여되어 검색에 용이하다. 

- 배열은 크기가 고정적이라는 단점이 있으며, index로 인해 데이터 삭제 시 재정렬 해야한다. 그러므로 데이터의 삽입과 삭제에는 용이하지 않다. 

---

3. Queue(큐) 

- 마치 줄을 서는 것과 같이, 먼저 들어온 데이터가 먼저 나가는(FIFO/LILO) 규칙을 갖고 있는 자료구조

- 이러한 규칙적 특성으로 인해, 데이터의 출입에 있어 재정렬이 필요없다. 

- 특별히 언급되는 장단점이 없으며, 주로 활용되는 예로 OS부분의 멀티 태스킹을 위한 프로세스 스케쥴링을 구현하기 위해 사용된다.

 

3-A) Queue의 종류

• 일반적인 Queue

• LIFO-Queue: 스택과 동일한 구조로, 나중에 입력된 데이터가 먼저 출력되는 구조(Last In, First Out)

• Priority-Queue: 키와 값을 쌍으로 한 구조의 데이터를 갖는 Queue로, 데이터와 함께 우선순위를 부여하여 우선순위가 높은 순으로 데이터가 출력된다. 

 

3-B) Queue 사용 시 알아야 하는 함수

• Queue.put(): 큐에 데이터를 넣는 함수

• Queue.get(): 큐에서 데이터를 꺼내는 함수

• Queue.qsize(): 큐의 크기를 확인하는 함수

• Enqueue(엔큐): 큐에 데이터를 넣는 기능

• Dequeue(디큐): 큐에서 데이터를 꺼내는 기능 

---

4. Stack(스택)

- 이름처럼 데이터를 쌓는 느낌으로, 데이터의 출입이 한쪽에서만 발생하는 구조

- 그러므로 가장 마지막으로 쌓인 데이터가 가장 먼저 나가는 규칙(LIFO)을 갖는다.

- 주로 활용되는 예로, 프로세스 실행 구조를 구현하는데 사용된다. 

 

4-A) Stack 장/단점

• 구조가 단순해서 구현이 쉽다.(장점)

• 데이터를 저장/읽기(검색) 속도가 빠르다.  → 프로세스 실행 구조로 사용하는 이유(장점)

• 데이터의 최대 개수를 미리 정해야 한다.(단점)

• 그렇기에 남는 공간이 생길 수 있다.(낭비 발생 - 이런 이유로 파이썬은 재귀함수를 1000번까지만 호출한다.)(단점)

---

5. Linked List(연결리스트)

- 배열(Array)의 단점이 보완된 자료구조로, 크기가 가변적인 배열이다. 

- 가변적인 크기를 구현하기 위해, 노드와 포인터를 사용하여 데이터를 저장하고 연결한다. 

- Node(노드): 연결리스트에서 사용하는 데이터의 저장단위로 value(값)과 포인터(주소값) 쌍으로 구성된다. 

- Pointer(포인터): 각 노드의 다음 노드가 갖고 있는 위치정보(주소값)를 의미한다.

 

5-A) 연결리스트의 장/단점

• 배열과 다르게 저장공간이 가변적이므로 저장공간을 미리 할당할 필요가 없다. (장점)

• 데이터간의 연결을 위한 포인터의 저장공간이 따로 필요하므로 저장공간효율이 안좋음. (단점)

• 특정 노드를 찾기 위해 각 노드의 포인터를 이용해 접근하기에 검색 속도가 느리다. (단점)

• 데이터를 삭제하면 삭제된 데이터의 다음과 이전 데이터의 연결을 재구성 해야한다. (단점)

---

6. Hash Table(해시 테이블)

- Hash Table은 key와 value를 쌍으로 구성하는 데이터를 저장하는 구조를 갖는다.

- key를 hash함수로 연산하여 value마다 독립적인 hash값/주소를 갖는다.  

- 이러한 특성으로 인해, 데이터 검색속도가 매우 빠르다. 

 

6-A) 알아야 하는 용어

• 해쉬(Hash): 임의 값을 고정된 길이로 변환하는 것
• 해쉬 테이블(Hash Table): 키 값에 대응하는 value를 갖고 있는 저장공간으로, 키 값을 기반으로 해시함수를 통해 직접 접근이 가능한 데이터 구조
• 해시 함수(Hash/Hashing Function): Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수
• 해쉬 값(Hash Value)/해쉬 주소(Hash Address): Key를 해시 함수로 연산하여 나온 결과값으로, Key에 대응하는 value의 저장공간에 대한 주소값을 의미한다. 이를 기반으로 해쉬 테이블에서 데이터(value)의 위치를 일관성있게 찾을 수 있다.
  - 쉽게 말해서, hash값은 배열의 index역할을 하는 것이다. 그러므로 절대로 중복되면 안된다.
• 슬롯(Slot): 한 개의 데이터를 저장할 수 있는 공간

 

6-B) Hash Table의 장/단점

1. 장점

- 데이터 저장/읽기 속도가 빠르다. (검색 속도가 빠르다.)
- 해쉬는 키에 대한 데이터 중복을 검증하기 쉽다.

2. 단점

- 해시테이블에 낭비되는 저장공간이 존재한다.

ex) value가 저장되어 있는 hash값이 0,4,5번 공간이라고 한다면 1,2,3번의 공간은 비어있다.  
- 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용하기에 공간과 탐색 시간을 맞바꾸는 기법이라고 표현한다.

- 공간을 탐색시간과 맞바꾼다는 의미: hash값(key값)의 중복 확률을 줄이기 위해 Hash Table의 저장공간을 크게 잡아서라도 Hash Table을 사용한다는 뜻이다. (검색속도가 빠르니 저장 공간을 더 소모해도 사용한다는 뜻)
- hash값 중복 및 충돌을 해결하기 위한 별도 자료구조가 필요하다. 

 

 

6-C) 주요 용도

- 검색이 많이 필요한 경우
- 저장, 삭제, 읽기가 빈번한 경우
- 캐쉬 구현시 (중복 확인이 쉽기 때문)

 

캐시(cache)란, 어떤 웹 페이지를 방문할 때마다 해당 웹 페이지의 모든 정보를 다운(로딩)받는 것은 시간을 많이 소모하기 때문에 고정적인 데이터들을 다운받아 놓고 동적으로 변하는 자료들을 그때마다 서버에서 받아 온다. 이 때, 다운받아 놓은 고정적인 데이터들을 저장하는 장소를 캐시라고 한다.

 

 

6-D) Hash Collision(충돌) 해결방법 - 좋은 Hash함수 사용하기

1) Chaining 기법

- Open Hashing(개방 해싱) 기법 중 하나로, Hash Table 저장공간 이외의 공간을 활용하는 기법이다. 

- 해시충돌이 발생하면 연결리스트를 사용하여 데이터를 추가로 뒤에 연결시켜 저장하는 방법이다. 

 

하지만, Hash Table로 인한 저장공간이 더욱 소모되는 상태에서 Chaining기법으로 인해 부가적인 저장공간을 사용해야 한다는 단점을 갖고 있다. 이를 보완한 기법이 Linear Probing 기법이다. 

 

2) Linear Probing 기법

- Close Hashing(폐쇄 해싱) 기법 중 하나로, 해싱충돌이 발생하면 Hash Table의 저장공간 안에서 충돌을 해결하는 기법이다. 

- 다시 말해, 충돌이 발생하면 Hash address를 이용하여 Hash Table의 빈공간을 찾아 저장하는 기법이다. 

- 이 기법을 사용하면 Hash Table의 저장공간 활용도를 높일 수 있다.

 

 

6-E) Hash Table사용 시, 꼭 알아두어야 하는 중요 사항

1) 빈번한 충돌을 개선하는 방법 - 해쉬 함수을 재정의 및 해쉬 테이블 저장공간을 확대

- 현재 정의된 hash table 저장공간의 50% 이상을 사용해야 한다면 충돌 확률이 커지기 때문에 hash table의 크기를 두 배이상 늘려야 한다. 

 

2) 파이썬의 hash() 함수는 실행할 때마다, 값이 달라질 수 있다.

- 그러므로 유명한 해쉬 함수들을 사용한다. ex) SHA(Secure Hash Algorithm, 안전한 해시 알고리즘)

- hash값을 가지고 원래 어떤 data로 생성된 것인지 알아낼 수 없어서 안전하다. 

- 어떤 데이터도 유일한 고정된 크기의 고정값을 리턴해주므로, 해쉬 함수로 유용하게 활용 가능

* SHA함수는 문자열을 반환하기 때문에 반드시 정수형으로 바꿔주어야 한다.

 

 

6-F) Hash Table의 시간복잡도

- 일반적인 경우(Collision 없음)는 O(1)

- 최악의 경우(Collision이 모두 발생)는 O(n)

 

* 해쉬 테이블의 경우, 일반적인 경우를 기대하고 만들기 때문에 시간복잡도는 O(1) 이라고 말할 수 있다.

* Collision(충돌)은 반드시 없애야 하는 것이다.

 

ex) 검색에서 해쉬 테이블의 사용 예

- 16개의 배열에 데이터를 저장하고, 검색할 때 O(n)

- 16개의 데이터 저장공간을 가진 위의 해쉬 테이블에 데이터를 저장하고, 검색할 때 O(1)

 

---

7. Tree(트리)

- node와 branch로 구성된 데이터 구조로, 사이클(순환)이 없다는 특징이 있다.

- Tree는 이진트리(Binary Tree)의 형태로 탐색(검색) 알고리즘 구현에 많이 사용된다. 

* 이진트리 - 하나의 node에서 뻗어나가는 branch의 수가 최대 2개인 트리 구조 

 

 

7-A) 이진 트리(Binary Tree)와 이진 탐색 트리(Binary Search Tree)

- 이진 트리: 하나의 node에서 뻗어나가는 branch의 수(자식노드)가 최대 2개인 트리

- 이진 탐색 트리: 왼쪽 노드는 반드시 오른쪽 노드보다 작은 값을 갖는 이진트리

 

 

7-B) 이진 탐색 트리의 장/단점과 주요 용도

- 장점: 데이터 탐색/검색에 용이하다.(탐색 속도를 개선) 

- 단점: 구현이 복잡하다.

---

8. Heap(힙)

- 트리구조에 기반을 둔 자료구조로, 저장된 데이터의 최대값 또는 최소값을 빠르게 찾기위해 고안된 완전이진트리(Complete Binary Tree) 

 

* 완전이진트리: 데이터가 삽입될 때, 왼쪽에 위치한 자식노드를 먼저 채우는 규칙을 갖는 이진트리

 

 

8-A) Heap을 사용하는 이유

- 우선순위 큐와 같이 최대값과 최소값을 빠르게 찾기위해 사용한다. 

- 이를 배열로 구현하면 최대값과 최소값을 찾는데 O(n)만큼 걸린다. 

- 반면에, heap을 이용하여 최대값과 최소값을 찾으면 O(log n)만큼 걸린다. 즉, 검색속도가 더 빠르다.

 

 

 

8-B) Heap의 종류

- Heap은 최대/최소 값을 구하기 위한 구조인 최대 힙(Max Heap)과 최소 힙(Min Heap)으로 분류할 수 있다. 

- Heap은 다음과 같은 조건을 갖고 있는 자료구조이다. 

• Max Heap의 경우, 각 노드의 값은 해당 노드의 자식노드가 가진 값보다 크거나 같다. 즉, 부모가 되는 노드가 자식노드보다 크거나 같은 값을 갖는다. 

• 반대로 Min Heap의 경우, 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 작거나 같다. 즉, 부모가 되는 노드가 자식노드보다 작거나 같은 값을 갖는다.  

• Heap은 완전이진트리의 형태를 갖는다.

- 위의 조건에 의해, Heap의 루트노드는 반드시 최대/최소값을 갖는다.

 

 

8-C) Heap과 이진탐색트리의 공통점 및 차이점

1. 공통점

- Heap과 이진탐색트리 모두 이진트리를 기반으로 하고있다. (자식노드가 최대 2개)

 

2. 차이점

- Heap은 부모노드의 값이 가장 크거나 같다(또는 가장 작거나 같다) 그러므로 자식노드 간의 크기비교에 대한 규칙이 존재하지 않는다.

- 반면에, 이진탐색트리는 왼쪽 자식노드(가장 작음) < 부모노드 < 오른쪽 자식노드(가장 큼) 순으로 규칙을 갖고있다.

- 이진탐색트리는 탐색(검색)을 위한 구조이며, Heap은 최대/최소값을 검색하기 위한 구조이다.  

 

 

8-D) Heap에서 사용하는 공식

- 부모노드의 인덱스 번호는 자식노드의 인덱스번호를 2로 나눈것의 몫(//) 이다. 여기서 2로 나누는 이유는 자식노드가 최대 2개까지만 존재하는 Heap의 완전이진트리 구조를 이용한 것이다.

 

* // 연산자: 몫을 구하는 연산자이다.

 

ex) 5번 노드의 부모 노드를 알고 싶다면 5/2의 몫 즉, 2가 되는 것이다. → 5//2 

ex) 3번 노드의 부모 노드를 알고 싶다면 3/2의 몫 즉, 1이 되는 것이다. → 3//2 

 

- 이러한 규칙성을 기반으로 Heap의 인덱스 번호를 구하기 위해 알아야 할 3가지 공식이 있다.

 

1. 부모 노드의 인덱스 = 자식노드 인덱스 // 2 

2. 좌측 자식 노드의 인덱스 = 부모 노드 인덱스 * 2 

3. 우측 자식 노드의 인덱스 = 부모 노드 인덱스 * 2 + 1 

(사칙연산은 곱셉과 나눗셈을 우선시 한다) 

 

 

8-E) Heap의 시간복잡도

- Heap의 depth(깊이/레벨)를 h라고 표기한다면, n개의 노드를 가지는 heap에 데이터를 삽입 또는 삭제할 때 최악의 경우 root노드에서 부터 leaf(terminal)노드까지 비교작업을 수행해야 하므로 h = log n에 가깝다. 그러므로 시간복잡도는 O(log n)이다. 다시 말해, 50%의 실행시간을 단축시킬 수 있다는 것을 의미함

 

* 참고: 빅오 표기법에서 log n 에서의 log의 밑은 10이 아니라, 2이다.