04.12 데이터 엔지니어링 3일차 - 자료구조/알고리즘 (3)

큐(Queues) 란?

먼저 집어넣은 데이터가 가장 먼저 나오는 FIFO(First In First Out)의 구조로 데이터를 저장하는 형식

 

큐의 추상적 자료구조 구현

1. 배열(array)을 이용하여 구현

 - python 리스트와 메서드들을 이용

2. 연결 리스트(linked list)를 이용하여 구현

 - 이전 강의에서 마련한 양방향 연결 리스트 이용

 

연산의 정의

• size() - 현재 큐에 들어 있는 데이터 원소의 수를 구함 (복잡도: O(1))
• isEmpty() - 현재 큐가 비어 있는지를 판단 (복잡도: O(1))
• enqueue(x) - 데이터 원소 x를 큐에 추가 (복잡도: O(1))
• dequeue() - 큐의 맨 앞에 저장된 데이터 원소를 제거 (또한, 반환) (복잡도: O(n))
• peak() - 큐의 맨 앞에 저장된 데이터 원소를 반환 (제거하지 않음) (복잡도: O(1))

 

큐 (Queue)의 활용

• 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로 (asynchronously) 일어나는 경우
• 자료를 생성하는 작업과 그 자료를 이용하는 작업이 양쪽 다 여러 곳에서 일어나는 경우
• 자료를 처리하여 새로운 자료를 생성하고, 나중에 그 자료를 또 처리해야 하는 작업의 경우

 

* 환형 큐 (Circular Queue): 정해진 개수의 저장 공간을 빙 돌려가며 이용

큐가 가득 차면? 더이상 원소를 넣을 수 없음 (큐 길이를 기억하고 있어야 함!!)

 

연산의 정의

큐와 동일하나 아래의 연산만 추가됨

• isFull() - 큐에 데이터 원소가 꽉 차 있는지를 판단

 

우선순위 큐 (Priority Queue)

•  큐가 FIFO (First-in First-Out) 방식을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져나오는 방식

 

우선순위 큐의 구현

- 서로 다른 두 가지 방식이 가능할 듯:

1. Enqueue 할 때 우선순위 순서를 유지하도록 - 이게 더 유리
2. Dequeue 할 때 우선순위 높은 것을 선택

- 서로 다른 두 가지 재료를 이용할 수 있음:

1. 선형 배열 이용
2. 연결 리스트 이용

---

트리(Trees) 란? 

정점(node)과 간선(edge)을 이용하여 데이터의 배치 형태를 추상화한 자료 구조

 

이진 트리 (Binary Trees)

트리에 포함되는 모든 노드의 차수가 2 이하인 트리, 모든 노드는 자식이 없거나 (리프노드의 경우), 하나만 있거나, 아니면 둘 있는 세 경우 중 하나에 해당

 

연산의 정의

• size() - 현재 트리에 포함되어 있는 노드의 수를 구함
• depth() - 현재 트리의 깊이 (또는 높이)를 구함
• 순회(traversal)

 

이진 트리의 순회 (Traversal)

• 깊이 우선 순회 (depth first traversal)
  • 중위 순회: left subtree -> 자기 자신 -> right subtree
  • 전위 순회: 자기 자신 -> left subtree -> right subtree
  • 후위 순회: left subtree -> right subtree -> 자기 자신
• 넓이 우선 순회 (Breadth First Traversal) : 수준(level)이 낮은 노드를 우선으로 방문
  • 수준 (level)이 낮은 노드를 우선으로 방문
  • 같은 수준의 노드들 사이에는, 부모 노드의 방문 순서에 따라 방문 + 왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문

단, 재귀적 (recursive) 방법은 적합하지 않음

 

이진 탐색 트리

모든 노드에 대해서, (중복되는 데이터 원소는 없는 것으로 가정)

• 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고
• 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰 성질을 만족하는 이진 트리