자료 구조

Deque

• Double Ended Queue
• 양방향 대기열

Deque의 구조

• Stack
  -LIFO(Last In First Out) : 나중에 들어간 데이터가 먼저 나오는 특성
  - 한 방향으로 데이터가 추가되고 삭제되는 형태
  - 먼저 저장된 데이터일수록 나중에, 나중에 들어간 데이터일수록 먼저 꺼낸다
• Queue
  • FIFO(First In First Out) : 먼저 들어간 데이터가 먼저 나오는 특징
    • 데이터가 한 방향으로 추가되고, 다른 방향으로 데이터가 삭제되는 형태
    • 먼저 들어간 데이터일수록 먼저, 나중에 들어간 데이터일수록 나중에 꺼낸다
• Deque
  • Stack과 Queue의 특성이 혼합되어 있는 구조
  • 양방향으로 열려있는 구조
  • Queue와 외형적으로 구조가 비슷하지만, LIFO / FIFO와 같은 순서에 구속되지 않는다

Deque의 특징

1. Stack 및 Queue를 모두 사용할 수 있다

• Deque는 양쪽으로 데이터를 추가 / 삭제할 수 있다
  • 그러므로 Stack, Queue를 구현할 수 있다
• 추가 및 삭제를 양쪽에서 제어할 수 있어 여러 형태로 사용이 가능하다

• 1. 추가를 제한하는 구조
  • 한쪽에서만 데이터 추가가 가능하고, 삭제는 양방향으로 가능하게 구현
    • 이 때, 데이터를 추가하는 방향에서 데이터를 삭제하는 형태는 Stack과 같고, 다른 방향에서 데이터를 삭제하는 형태는 Queue와 같다

• 2. 삭제를 제한하는 구조
  • 한쪽에서만 데이터 삭제가 가능하고, 추가는 양방향으로 가능하게 구현
    • 이 때, 데이터를 삭제하는 방향에서 데이터를 추가하는 형태는 Stack과 같고, 다른 방향에서 데이터를 추가하는 형태는 Queue와 같다

2. 양방향 끝에서 데이터 추가, 삭제가 용이하다

• Stack과 Queue는 추가할 데이터나 삭제할 데이터의 인덱스 정보를 갖고 있다
• Deque는 양쪽의 추가 / 삭제할 데이터의 인덱스 정보를 가지고 있어 양쪽 끝의 데이터에 접근 / 추가 / 삭제가 용이하다

3. 양방향 끝이 아닌 임의의 데이터만 추가하거나 삭제하는 건 불가능하다

• Deque는 양방향 끝의 인덱스 정보를 갖는다
  • 중간에 있는 데이터에 접근하려고 할 때, 양쪽 끝 이외의 인덱스 정보가 없으므로 접근할 수 없다
  • 그러므로 임의의 인덱스만 추가 / 삭제하는 것은 불가능하다

---

Linked List

Linked List의 정의

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

Linked List의 구조

• 배열(Array) vs Linked List
  • 배열(Array)
    • 연속된 공간 안에 메모리를 차지한다
    • 인덱스를 통해 각 요소의 데이터를 읽거나 쓸 수 있는 자료 구조
    • 연속된 메모리 주소값 안에 데이터를 넣어, 위치를 바꿀 때 데이터가 이동해야 한다
  • Linked List
    • 흩어져 있는 공간에 노드들의 연결로 이루어진 자료 구조
    • 하나의 노드에는 데이터와 다음 노드의 주소가 담겨 있다
    • 각 노드가 다음 노드의 주소값을 가지고 있어야 다음 노드를 접근할 수 있다
      • 마지막 노드는 null을 가리킨다

Linked List의 특징

1. 노드의 추가 및 삭제가 빠르고 쉽다

• 배열(Array)
  • 연속된 메모리 상에 데이터가 저장되어 있다
    • 그러므로 값을 추가하거나 삭제할 때에는 메모리에 재할당을 해줘야 한다
  • 중간에 데이터를 추가한다면, 마지막 인덱스를 새로 만들어 마지막 데이터부터 삽입하고자 하는 인덱스의 데이터까지 모두 한 칸씩 이동이 필요하다
    • 마지막 인덱스에 데이터를 추가한다면 O(1)의 시간 복잡도를 보인다
    • 그러나 0번 인덱스에 데이터를 추가한다면, 모든 데이터를 옮겨야하므로 O(N)의 시간 복잡도를 보인다
  • 삭제도 추가와 마찬가지로 마지막 요소부터 삭제하려는 인덱스 전 데이터까지 모두 한 칸씩 이동이 필요하다

• Linked List
  • 각 노드들이 메모리 상에 흩어져 존재한다
    • 각 노드는 다음 노드의 주소값을 갖는다
    • 그러므로 데이터를 담은 노드를 어디에도 손쉽게 추가 / 삭제할 수 있다
  • 중간에 데이터를 추가한다면, 노드가 가리키는 다음 노드의 메모리 주소만 변경해주면 되므로 쉽게 추가할 수 있다
  • 삭제 역시 마찬가지로 노드가 가리키는 다음 노드의 메모리 주소만 변경해주면 된다
    • 그러므로 어떤 위치에 노드를 추가 / 삭제해도 O(1)의 빠른 시간 복잡도를 보인다

2. 노드의 값을 찾으려면 최대 전체를 순회해야 한다

• 배열(Array)
  • 연속된 메모리 상에 데이터가 저장되어 있다
    • 그러므로 인덱스를 통해 주소의 계산이 쉬워 쉽게 접근할 수 있다
    • 데이터에 접근하는 데에 O(1)의 시간 복잡도를 보인다

• Linked List
  • head node : Linked List의 첫 번째 노드
  • 순회하기 전까지는 head node에 대한 정보만 갖고 있다
    • 그러므로 필요한 값이 있는지 확인하려면 head node부터 연결된 다음 노드들을 접근해야 한다
    • 만약 찾으려는 값이 가장 마지막에 존재한다면 N개의 노드를 모두 순회해야 한다
    • 데이터에 접근하는데에 head node에 있는 값은 O(1)의 시간 복잡도를 보이지만, 마지막 요소에 접근하기 위해서는 O(N)의 시간 복잡도를 보인다

Linked List의 실사용 예제

• 삽입 및 삭제가 중요한 곳에 활용된다
  • join, split 메서드와 같이 데이터 삽입 및 삭제가 중요한 메서드의 구현에도 활용할 수 있다
• 동적 기억장소 관리
  • 실행되는 작업에 필요한 크기만큼의 메모리를 할당하는 방법에 활용한다
• Garbage Collection
• Hash Table의 충돌 시 해결법 중 chaining 방법을 사용할 때, Linked List를 활용한다

---

Hash Table

Hash Table의 정의

• 해시 함수(hash Function)를 사용하여 변환한 해시(hash)를 색인(index)으로 삼아 키(key)와 데이터(data)를 저장하는 자료 구조
  • 필요한 데이터의 키(key)를 해시 함수(hash Function)를 사용해 별도의 해시(hash)로 바꿔주고, 해당하는 데이터(value)를 함께 저장하는 자료 구조

Hash Table의 구조

• 키(key)와 해시 함수(hash function), 해시(hash), 데이터(value)로 이루어져 있다
  • 키(key)
    • 고유한 값
    • 해시 함수의 입력값이 된다
    • 다양한 길이의 값이 들어올 수 있다
      • 그러므로 해시 함수를 통해 변환하지 않은 상태로 저장소에 저장되면 다양한 길이만큼의 저장소를 구성해두어야 한다
      • 이로 인해 우리는 해시 함수로 값을 바꾸어 저장한다
  • 해시 함수(hash function)
    • 키(key)를 해시(hash)로 바꿔주는 역할을 한다
    • 다양한 길이를 가지는 키(key)가 해시 함수를 거쳐 일정한 길이를 가지는 해시(hash)로 변경된다
      • 일정한 길이의 해시로 변경되어 저장소를 운영할 때 효율적으로 운영할 수 있게 된다
    • 해시 충돌(Hash Collision)
      • 서로 다른 키(key)가 같은 해시(hash)가 되는 경우를 뜻한다
      • 다양한 길이의 키를 일정한 길이의 해시로 줄이다보니 다른 키가 같은 해시가 되는 경우가 존재한다
      • 해시 충돌을 일으키는 확률을 최대한 줄이는 해시 함수를 만드는 것은 중요하다!
  • 해시(hash)
    • 키(key)가 해시 함수(hash function)를 거쳐 만들어진 결과물
    • 저장소에서 데이터(value)와 매칭되어 저장된다
    • 변환된 값을 배열의 색인(index)과 같이 사용한다
  • 데이터(value)
    • 저장소에 최종적으로 저장되는 값
    • 색인(index)과 매칭되어 저장된다

Hash Table의 특징

• 장점
  1. 저장 / 삭제 / 검색 과정은 모두 평균적으로 O(1)의 시간 복잡도를 보인다
     • 그러므로 데이터를 다루는 작업이 매우 빠르다
• 단점
  1. 해시 충돌이 발생할 수 있다
  2. 데이터가 저장되기 전에 미리 저장공간을 만들어놔야하므로 공간 효율성이 떨어진다
  3. 해시 함수(hash function)의 의존도가 높다
     • 해시 함수(hash function)가 복잡하다면 해시(hash)값을 만드는 데에 많은 시간이 소요된다

저장, 삭제, 검색 과정

1. 해시 함수(hash function)에 키(key)값을 넣어 해시(hash)값을 만든다
2. 만들어진 해시(hash)값과 일치하는 색인(index)을 찾아 저장하거나 삭제, 검색한다

• 기본적으로 각 작업들의 시간복잡도는 O(1)
  • 해시 함수(hash function)를 거쳐 해시(hash)값을 찾아내는데 걸리는 과정은 고려하지 않는다
  • 해시 충돌이 발생할 경우, 데이터를 저장할 때에는 저장소의 모든 색인을, 데이터를 삭제 / 검색할 때에는 모든 데이터(value)를 찾아봐야 하므로 O(n)이 된다

대표적인 해시 알고리즘

Division Method

• Number 타입의 키(key)를 저장소의 크기로 나누어 나온 나머지를 색인(index)으로 사용하는 알고리즘
• 저장소의 크기는 소수(prime number)로 정하고, 2의 제곱수와 거리가 먼 값을 사용하는 것이 효과적이다

Digit Folding

• 키(key)의 문자열을 ASCII 코드 값으로 변경하고 그 값을 합해 저장소에서 색인(index)으로 사용하는 방법
• 색인(index)이 저장소의 크기를 넘는다면 Division Method를 적용할 수 있다

Multiplication Method

• 숫자로 된 key값 K와 0과 1 사이의 실수 N, 보통 2의 제곱수인 M을 사용하여 다음과 같은 식을 통해 계산한 값을 색인(index)으로 사용하는 기법
  • index = (KN mode 1)M

Universal Hashing

• 다수의 해시 함수(hash function)를 만들어 특정 장소에 넣어두고, 무작위로 해시 함수를 선택해 해시(hash) 값을 생성하는 기법

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

1. 개방 연결법(Open Addressing)

• 해시 충돌이 발생하면 다른 색인(index)에 해당 자료를 삽입하는 방식
• 개방 연결법의 방법들
  • 1. Linear Probing
    • 중복된 색인(index)으로부터 고정된 숫자만큼 이동하면서 비어있는 저장소(버킷)를 찾아 해당 저장소(버킷)에 값을 저장하는 방법
  • 2. Quadratic Probing
    • 중복된 색인(index)으로부터 이동할 숫자를 제곱으로 사용하는 방법
    • 처음 충돌이 발생한다면 $1^2$만큼 이동하고, 또 충돌이 발생한다면 $2^2$만큼 이동하며, 또 충돌이 발생하면 $3^3$만큼 이동한다
  • 3. Double Hashing Probing
    • 하나의 해시 함수(hash function)에서 충돌이 발생하면 미리 지정해둔 다른 해시 함수(hash function)를 이용해 새로운 주소를 받아 사용하는 방법
    • 다른 방법들보다 더 많은 연산을 필요로 한다

2. 분리 연결법(Seperate Chaining)

• 동일한 색인(index)의 데이터에 대해 연결 리스트(Linked List), 트리(Red-Black Tree) 등의 자료 구조를 활용하여 데이터의 주소를 저장하는 방법
  • 동일한 버킷의 데이터에 연결 리스트(Linked List)나 트리(Red-Black Tree)와 같은 자료 구조를 사용하여 충돌이 일어난 데이터를 저장한다

• 장점
  • 구현이 간단하다
  • 데이터(value)를 쉽게 삭제할 수 있다
• 단점
  • 중복으로 저장되는 데이터(value)가 많아지면, 동일한 버킷에 연결되는 데이터(value)가 많아져 검색의 효율성이 떨어진다

3. 저장소 확장(Resize)

• 일정 이상의 저장소를 사용한다면 저장소의 크기를 늘리는 방법
  • Ex. HashMap 자료 구조는 매치된 key-value 데이터의 개수가 일정 이상이 된다면(저장소의 75% 이상 사용), 저장소의 크기를 두 배로 늘린다
    • 저장소 크기가 작다면, 불필요한 메모리 사용을 줄일 수 있지만 해시 충돌이 발생하여 개방 연결법이나 분리 연결법을 사용해도 성능상 손실이 발생한다
    • 저장소 확장 방식을 통해 해시 충돌로 인한 성능이 감소하는 문제를 어느 정도 해결할 수 있다

실사용 예제

• 주소록
• 블록 체인
• 자바스크립트 실행 엔진(크롬, V8)
• DNS 변환

---

Heap Tree

Heap Tree 정의

• 트리 구조로 구현된 자료 구조
• 우선 순위에 따라 빠르게 자료를 검색할 수 있는 구조
  • 우선 순위를 정해 먼저 자료를 찾아내고 처리하기 위해 만들어진 자료 구조이다
• 우선 순위 큐, 힙 정렬 등에 Heap Tree가 사용된다

Heap Tree 구조

• Heap Tree는 느슨한 정렬 구조로 구현되어 있다
  • 느슨한 정렬 구조
    • 부모 노드의 값은 자식 노드의 값보다 항상 크거나(최대 힙) 항상 작게(최소 힙) 정렬되어 있다
    • 자식 노드끼리의 값의 크기에 따라 좌우 위치는 정렬하지 않는다
    • 그러므로 느슨한 정렬 구조라고 표현한다

Heap Tree의 특징

1. 완전 이진 트리

• 완전 이진 트리로 구성되어 있다
• 최댓값 / 최솟값을 찾기 위해서는 완전 이진 트리를 구성할 필요가 없지만, 삽입 / 삭제 시에 성능을 위해 완전 이진 트리로 구현한다

2. 중복된 값 저장

• Heap Tree는 중복된 값을 저장할 수 있다
  • 최댓값 / 최솟값을 찾아내기 위한 구조이기 때문에 중복된 값이 저장되어도 상관 없다

3. 최대 힙 / 최소 힙

• Heap Tree 자료 구조는 최대 힙 / 최소 힙으로 구현한다
  • 최대 힙
    • 루트 노드에 가장 큰 값이 위치하고 자식 노드로 내려갈수록 작은 값이 위치한다
  • 최소 힙
    • 루트 노드에 가장 작은 값이 위치하고 자식 노드로 내려갈수록 큰 값이 위치한다

Heap Tree의 데이터 처리 방식

1. 데이터 검색(최대값 / 최소값)

• 최대 힙일 경우, 최댓값을 찾는 데에 걸리는 시간 복잡도는 O(1)이다
  • 최대 힙일 경우에는 Heap Tree의 특성에 따라 루트 노드의 값이 가장 큰 값이다
    • 그러므로 루트 노드의 값을 불러오기만 하면 된다
• 최소 힙일 경우, 최솟값을 찾는 데에 걸리는 시간 복잡도는 O(1)이다
  • 최소 힙일 경우에도 마찬가지로 Heap Tree의 특성에 따라 루트 노드의 값이 가장 작은 값이다
    • 그러므로 루트 노드의 값을 불러오기만 하면 된다

2. 데이터 삽입

• 데이터 삽입 과정
  1. 가장 마지막 노드에 새로운 값을 저장한다
  2. 삽입된 노드의 값과 부모 노드의 값을 비교한다
  3. 최소 힙 / 최대 힙인지에 따라 부모의 값과 위치를 서로 변경한다
     • 최소 힙일 때는, 부모의 값이 더 크다면 부모의 값과 위치를 서로 변경한다
     • 최대 힙일 때는, 부모의 값이 더 작다면 부모의 값과 위치를 서로 변경한다
  4. 더 이상 위치가 바뀌지 않을 때까지 위의 1 ~ 3번 과정을 반복한다

3. 데이터 삭제

• 데이터 삭제 과정
  1. 루트 노드의 값을 제거한다
  2. 루트 노드 자리에 마지막 노드의 값을 삽입한다
  3. 루트 노드 자리로 올라온 노드의 값과 자식 노드들의 값과 비교한다
  4. 최소 힙 / 최대 힙인지에 따라 자식의 값과 위치를 서로 변경한다
     • 최소 힙일 때는, 부모보다 더 작은 자식이 있다면 해당 자식의 값과 위치를 교환한다(만약 두 자식의 값이 모두 부모보다 작다면, 두 값 중 더 작은 값과 위치를 교환한다)
     • 최대 힙일 때는, 부모보다 더 큰 자식이 있다면 해당 자식의 값과 위치를 교환한다(만약 두 자식의 값이 모두 부모보다 크다면, 두 값 중 더 큰 값과 위치를 교환한다)
  5. 더 이상 작은/큰 값이 없을 때까지 반복한다

Heap Tree를 배열로 구현하기

• Heap Tree는 완전 이진 트리로 구현되어 있어 중간에 빈 값이 없다
  • 그러므로 루트 노드부터 높이 순서대로 뱅려에 모두 정렬이 가능하다
  • 보통 구현과 노드의 위치를 찾기 쉽게 하기 위해 0번째 인덱스는 사용하지 않고, 첫 번째 인덱스부터 사용한다
  • 높이 순서대로 배열에 값을 저장하는데, 좌에서 우로 순서대로 값을 저장한다

• 배열을 통해 알 수 있는 정보
  • 깊이(depth)
    • 1, 3, 7, 15, ... 와 같이 2의 배수를 계속 더한만큼 깊이가 늘어난다
  • 자식 노드의 인덱스
    • 왼쪽 자식 : 현재 노드의 인덱스 * 2
    • 오른쪽 자식 : 현재 노드의 인덱스 * 2 + 1
  • 부모 노드의 인덱스
    • Math.floor(자식 노드의 인덱스 / 2)

---

검색 알고리즘(Search Algorithm)

트리 순회(Tree Traversal)

• 특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것
• 트리 구조는 계층적 구조를 가진다
  • 모든 노드를 순회하는 방법
    1. 전위 순회
    2. 중위 순회
    3. 후위 순회
  • 트리 구조에서 노드를 순차적으로 조회할 때에는 왼쪽에서 오른쪽으로 조회한다

트리 순회 방법

• 전위 순회(Preorder Traverse)
  • [루트 노드 - 왼쪽 자식 - 오른쪽 자식] 순으로 순회
  • 위 그림을 전위 순회로 순회하면 다음과 같은 순서로 순회한다
    • 1 - 2 - 4 - 8 - 9 - 5 - 10 - 3 - 6 - 11 - 7

• 중위 순회(Inorder Traverse)
  • [왼쪽 자식 - 루트 노드 - 오른쪽 자식] 순으로 순회
  • 위 그림을 중위 순회로 순회하면 다음과 같은 순서로 순회한다
    • 8 - 4 - 9 - 2 - 5 - 10 - 1 - 6 - 11 - 3 - 7

• 후위 순회(Postorder Traverse)
  • [왼쪽 자식 - 오른쪽 자식 - 루트 노드] 순으로 순회
  • 위 그림을 후위 순회로 순회하면 다음과 같은 순서로 순회한다
    • 8 - 9 - 4 - 10 - 5 - 2 - 11 - 6 - 7 - 3 - 1

---

BFS / DFS

그래프의 탐색

• 하나의 정점에서 시작하여 그래프의 모든 정점을 한 번씩 방문(탐색)
• 그래프의 데이터는 정렬되어 있지 않다
  • 그러므로 원하는 자료를 찾으려면 모두 방문하여 찾아야 한다

• 대표적인 그래프의 탐색 방법
  • DFS
  • BFS
    • 두 방법 모두 모든 정점을 한 번씩 방문한다

너비 우선 탐색(Breadth-First Search, BFS)

• 너비를 우선적으로 탐색하는 방법
• 주로 두 정점 사이의 최단 경로를 찾을 때 사용한다
  • 만약, 경로를 하나씩 전부 방문한다면, 최악의 경우에 모든 경로를 다 살펴보아야 한다
• 위 그림을 BFS로 탐색한다면 아래와 같은 순서로 탐색한다
  • 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11

깊이 우선 탐색(Depth-First Search, DFS)

• 깊이를 우선적으로 탐색하는 방법
• 한 정점에서 시작해 다음 경로로 넘어가기 전에 해당 경로를 모두 탐색할 때 사용한다
• BFS보다 탐색 시간은 조금 오래 걸릴 수 있다
  • 그러나, 모든 노드를 완전히 탐색할 수 있다
    • 만약 찾으려는 경로가 첫 번째 경로라면, DFS는 해당 경로를 탐색한 후 종료되겠지만, BFS는 다른 모든 경로를 살펴보게 된다
• 위 그림을 DFS로 탐색한다면 아래와 같은 순서로 탐색한다
  • 1 - 2 - 4 - 8 - 9 - 5 - 10 - 3 - 6 - 11 - 7