자료구조 기본 2

자료구조 기본

자료구조

Deque

Deque는 Double Ended Queue의 양방향 대기열이라고도 불리는 자료 구조이다. 현실 세계의 비슷한 예를 든다면, 실의 양쪽에 구슬을 꿰어 넣는 것과 비슷한 구조로 되어 있다.

Deque의 구조

Deque는 Stack과 Queue의 특성들이 혼합되어 있다.

양방향으로 열려있는 구조로, Queue와 외형적으로 비슷한 구조이다. 그러나 Deque는 한 방향인 Stack과 Queue와 달리 LIFO, FIFO와 같은 순서에 구속되지 않는다.

Deque의 특징

1. Stack 및 Queue를 모두 사용할 수 있다.
2. 양방향 끝에서 데이터 추가, 삭제가 용이하다.
3. 양방향 끝이 아닌 임의의 데이터만 추가하거나 삭제하는 건 불가능하다.

---

Linked List

Linked List 자료 구조는 선형으로 그룹화된 데이터의 집합으로 데이터와 다음 데이터의 주소를 포함하고 있는 하나의 노드가 선형으로 연결된 자료 구조이다.

Linked List의 구조

Linked List 자료 구조는 연속된 공간이 아니라 흩어져 있는 공간에 노드들의 연결로 이루어진 자료 구조이다. 하나의 노드에는 데이터와 다음 노드의 주소가 담겨있다. 그리고 각 노드는 다음 노드를 가리킨다. 연속된 메모리 주소가 아니기 때문에 직접 주솟값을 가지고 있어야 다음 노드로 접근할 수 있다. 마지막 노드는 다음을 가리킬 곳이 없으므로 새로 추가되기 전까지는 null을 가리킨다.

Linked List의 특징

1. 노드의 추가와 삭제가 빠르고 쉽다.
   • 순서가 지정되지 않은 특성 때문에 데이터를 담은 노드를 어디에도 손쉽게 추가하거나 삭제할 수 있다.
2. 노드의 값을 찾으려면 최대 전체를 순회해야 한다.
   • Linked List의 노드는 메모리에 흩어져 있어서 특정 노드로 쉽게 접근할 수 없다.
   • Linked List의 첫 번째 노드를 head node라고 하며 순회하기 전까지는 head node의 정보만 알고 있다. 필요한 값이 있는지 확인하려면 head node에 연결된 다음 노드로 접근해야 하고, 접근한 노드에 원하는 값이 없다면 다시 다음 노드로 이동해야 한다.

---

Hash Table

Hash Table이란 해시함수(hash function)를 사용하여 변환한 해시(hash)를 색인(index)으로 삼아 키(key)와 데이터(value)를 저장하는 자료 구조이다.

이는 필요한 데이터의 키를 해시함수를 사용해 별도의 해시로 바꿔 주고, 해당하는 데이터를 함께 저장하는 자료 구조이다.

Hash Table의 구조

• 키(key) : 고유한 값으로 해시 함수의 입력값이 된다. 다양한 길이의 값이 들어올 수 있다. 해시 함수를 통해 변환하지 않은 상태로 저장소에 저장이 되면 다양한 길이만큼의 저장소를 구성해 두어야 하기 때문에 해시 함수로 값을 바꾸어 저장하게 된다.
• 해시함수(hash function) : 키를 해시로 바꿔주는 역할을 한다. 다양한 길이를 가지고 있는 키를 일정한 길이를 가지는 해시로 변경하여 저장소를 효율적으로 운영할 수 있도록 도와준다. 다만, 서로 다른 키가 같은 해시가 되는 경우를 해시 충돌이라고 하는데, 해시 충돌을 일으키는 확률을 최대한 줄이는 것이 중요하다.
• 해시(hash) : 키를 해시함수를 사용하여 만들어진 결과물로, 저장소에서 데이터와 매칭되어 저장된다. 변환된 값을 배열의 색인과 같이 사용하게 된다.
• 데이터(value) : 저장소에 최종적으로 저장되는 값으로 색인과 매칭되어 저장된다.

Hash Table의 특징

Hash Table에서 저장, 삭제, 검색 과정은 모두 평균적으로 O(1)의 시간복잡도를 가지고 있어 데이터를 다루는 작업이 매우 빠르다는 장점이 있다.

다만, 해시 충돌이 발생할 수 있고 데이터가 저장되기 전에 저장공간을 미리 만들어놔야 하기 때문에 공간 효율성이 떨어진다. 또한 해시함수의 의존도가 높다.

이 말은 곧, 해시 함수가 복잡하다면, 해시값을 만들어내는 데 많은 시간이 소요된다.

1. 저장, 삭제, 검색 과정
   Hash Table에서 값을 저장, 삭제, 검색하기 위해서는 해시 함수에 키값을 넣어 해시값을 만들게 된다. 이후 만들어진 해시값과 일치하는 색인을 찾아 저장하거나 삭제, 검색한다.
   
   기본적으로 해당 작업들의 시간복잡도는 O(1)이다.
   
   해시함수를 거쳐 해시값을 찾아내는데 걸리는 과정은 고려하지 않는다. 그러나 해시 충돌이 발생할 경우 저장소의 모든 색인(삽입) 혹은 데이터(삭제, 검색)를 찾아봐야 하기 때문에 O(n)이 된다.

2. 대표적인 해시 알고리즘

• Division Method : Number type의 키를 저장소의 크기로 나누어 나온 나머지를 색인으로 사용하는 방법이다. 이때 저장소의 크기를 소수(Prime Number)로 정하고 2의 제곱수와 먼 값을 사용하는 것이 효과가 좋다.
• Digit Folding : 키의 문자열을 ASCII 코드로 바꾸고 그 값을 합해 저장소에서 색인으로 사용하는 방법이다. 만약, 이때 색인이 저장소의 크기를 넘어간다면 Division Method를 적용할 수 있다.
• Multiplication Method : 숫자로 된 키값 K와 0과 1 사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 다음과 같이 계산한 값을 사용한다. index = (KA mod 1)m
• Universal Hashing : 다수의 해시함수를 만들어 특정한 장소에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만드는 기법이다.

해시 충돌을 해결할 수 있는 방법

1. 개방 연결법(Open Addressing)
   • 개방 연결법이란 해시 충돌이 발생하면 다른 색인에 해당 자료를 삽입하는 방식으로 대표적으로 사용되는 세 가지 방법이 있다.
   1. Linear Probing
      • 현재 중복된 색인으로부터 고정된 숫자만큼 이동하여 비어있는 저장소(버킷)를 찾아 데이터를 저장한다
   2. Quadratic Probing
      • 현재 중복된 색인으로부터 이동할 숫자를 제곱으로 사용하는 방식이다. 처음 충돌이 발생하면 1(1^2)만큼 이동하고, 또 충돌이 발생한다면 4(2^2)만큼, 3번째는 9(3^2)만큼, 4번째는 16(4^2)만큼 이동하여 빈 공간을 탐색하는 방법이다.
   3. Double Hashing Probing
      • 하나의 해시함수에서 충돌이 발생한다면 미리 지정해둔 다른 해시함수를 이용해 새로운 주소를 받아 사용하는 방법으로 다른 방법들보다 많은 연산이 필요하게 된다.
2. 분리 열결법(Seperate Chaining)
   • 분리 연결법이란 동일한 색인의 데이터에 대해 연결리스트, 트리 등의 자료 구조를 활용해 데이터의 주소를 저장하는 방법이다.
   • 구현이 간단하며, 데이터를 쉽게 삭제할 수 있다는 장점이 있다. 하지만 중복으로 저장되는 데이터가 많아지면 동일한 버킷에 연결되는 데이터가 많아져서 검색의 효율성이 감소하는 단점이 있다.
3. 저장소 확장(Resize)
   • 저장소의 크기가 작다면 불필요한 메모리 사용을 줄일 수 있지만, 해시 충돌이 발생하며 개방 연결법이나 분리 연결법을 사용해도 성능상 손실이 발생한다. 실제 Java에서 사용되는 HashMap이라는 자료 구조는 매치된 key-value 데이터 개수가 일정 이상이 된다면(저장소의 75% 이상 사용) 저장소의 크기를 두 배로 늘리게 된다. 이 방식으로 해시 충돌로 인한 성능이 감소하는 문제를 어느 정도 해결이 가능하다.

---

Heap Tree

Heap Tree는 트리 구조로 구현된 자료 구조이다. 일반적인 트리 구조와는 다르게, 우선순위에 따라서 빠르게 자료를 검색할 수 있는 구조이다.

Heap Tree의 구조

Heap Tree는 느슨한 정렬 구조로 구현되어 있다.

• 느슨한 정렬 구조
  • 부모 노드의 값은 자식 노드의 값보다 항상 크거나 항상 작게 정렬되어 있다. 하지만 자식 노드끼리의 값의 크기에 따라 좌우 위치는 정렬하지 않기 때문에, 느슨한 정렬 구조라고 표현한다.

Heap Tree의 특징

1. 완전 이진 트리
   • 완전 이진 트리로 구성되어 있다. 단순히 최대값, 최소값을 찾기 위해서는 완전 이진 트리로 구성할 필요는 없지만, 삽입/삭제 시 성능을 위해 완전 이진 트리로 구현하게 된다.
2. 중복된 값 저장
   • 일반적인 이진 탐색 트리와 다르게 중복된 값을 저장할 수 있다.
3. 최대 힙 / 최소 힙
   • 최대 힙 : 루트 노드에 가장 큰 값이 위치하며 자식 노드로 내려갈수록 작은 값이 위치하게 구현
   • 최소 힙 : 루트 노드에 가장 작은 값이 위치하며 자식 노드로 내려갈수록 큰 값이 위치하게 구현

Heap Tree의 데이터 처리 방식

1. 데이터 검색(최대값/최소값)
   • 최대 힙일 경우 최대값을 찾는데 걸리는 시간복잡도는 O(1)이다. Heap Tree의 특성상 최대 힙일 경우 항상 루트 노드의 값이 가장 큰 값이기 때문에, 최대값은 항상 루트 노드의 값을 불러오기만 하면 된다.
   • 최소 힙일 경우 루트 노드의 값이 가장 작은 값이기 때문에 시간복잡도는 O(1)이다.
2. 데이터 삽입
   1. 가장 마지막 노드에 새로운 값을 저장한다.
   2. 삽입된 노드의 값과 부모 노드의 값을 비교한다.
   3. 최대 힙일 경우, 부모의 값이 더 크다면 부모의 값과 위치를 서로 변경한다.
   4. 더 이상 위치가 바뀌지 않을 때까지 1~3까지의 과정을 반복한다.
3. 데이터 삭제
   1. 루트 노드의 값을 제거한다.
   2. 루트 자리에 마지막 노드의 값을 삽입한다.
   3. 올라간 노드의 값과그 자식 노드들의 값과 비교한다.
   4. 부모보다 더 큰 자식이 있다면(최대 힙) 해당 자식의 값과 서로 교환한다.
      (만약 두 자식의 값이 모두 부모보다 작다면, 두 값 중 큰 값과 위치를 변경한다.)
   5. 더 이상 큰 값이 없을 때까지 반복한다.

Heap Tree를 배열로 구현하기

• Heap Tree는 완전 이진 트리로 구현되어 배열로 표현할 수 있다.
• 완전 이진 트리의 특성상 중간에 빈 값이 없기 때문에 루트 노드부터 높이 순서대로 배열에 모두 정렬이 가능하다.
• 구현과 노드의 위치를 찾기 쉽게 하기 위해 일반적으로 배열의 0번째 인덱스는 사용하지 않고, 첫 번째 인덱스부터 사용한다.
• 높이 순서대로 배열에 값을 저장하며, 좌에서 우로 순서대로 값을 저장한다.
• 배열로 Heap Tree를 구현한다면 배열의 크기에 따라서 Heap Tree의 depth가 얼마인지, 부모와 자식 노드의 위치까지도 쉽게 검색할 수 있다.
• depth는 배열의 길이가 1, 3, 7, 15 순서대로 2의 배수를 계속 더한 만큼 depth가 늘어난다.
• 부모와 자식 노드의 인덱스를 찾는 방법도 수식으로 계산할 수 있다.