✏️ 오늘 학습한 내용
1. Queue
2. Circular Queue
3. Priority Queue
4. Binary Tree
5. Binary Search Tree
6. Heap
🔎 Queue
1) Queue의 구조
- 자료를 보관할 수 있는 선형 구조
- FIFO(First In First Out) : 처음에 넣은 것을 먼저 빼는 방식
- enqueue : 한 쪽 끝에서 넣음
- dequeue : 반대 쪽에서 뽑아 꺼냄
2) 연산의 정의
- size() : 현재 큐에 들어 있는 데이터 원소의 수를 구함
- isEmpty() : 현재 큐가 비어 있는지를 판단
- enqueue(x) : 데이터 원소 x를 큐에 추가
- dequeue() : 큐의 맨 앞에 저장된 데이터 원소를 제거(후 반환)
- peek() : 큐의 맨 앞에 저장된 데이터 원소를 반환(제거하지는 않음)
3) Array 구현과 Doubly Linked List 구현의 차이
- Array : dequeue() 연산이 배열의 위치를 순차적으로 변경해야하므로 O(N)의 시간복잡도를 가진다.
- Doubly Linked List : dequeue()에 대해 O(1)의 시간복잡도를 갖지만, 탐색에는 O(N)의 시간복잡도를 갖는다.
4) Queue가 활용되는 경우
- 자료를 생성하는 작업이 여러 곳에서 일어나는 경우
- 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로 일어나는 경우
- 자료를 생성하는 작업과 그 자료를 이용하는 작업이 양쪽 다 여러 곳에서 일어나는 경우
🔎 Circular Queue
1) Circular Queue란
정해진 개수의 저장 공간을 빙 돌려가면서 이용하는 Queue의 일종
2) Circular Queue가 사용되는 예시
상황 : 네트워크 인터페이스를 통해 도착하는 패킷들을 Queue에 쌓고 도착한 순서대로 적절한 응용 프로그램에게 데이터를 보내주는 기능을 구현하려는 경우
문제 : Queue에 담을 수 있는 데이터의 양은 무한하지 않고,
선형적인 Queue의 경우 구조상 dequeue()를 할때마다 front가 앞으로 진행되면서 front가 진행된 공간이 활용되지 못하게 되어 비효율적이다.해결방안 : Queue 크기의 상한을 미리 정하고, Queue를 원형으로 만들고 front(입구), rear(출구) 인덱스를 기억해둔다면, 데이터의 원소가 빠져 나간 쪽의 저장소를 재활용하면서 큐를 관리할 수 있다.
( Circular Queue를 사용 )
3) Circular Queue 구현
class CircularQueue:
def __init__(self, n):
self.maxCount = n
self.data = [None] * n
self.count = 0
self.front = -1
self.rear = -1
def size(self):
return self.count
def isEmpty(self):
return self.count == 0
def isFull(self):
return self.count == self.maxCount
def enqueue(self, x):
if self.isFull():
raise IndexError('Queue full')
self.rear =
(self.rear + 1) % self.maxCount
self.data[self.rear] = x
self.count += 1
def dequeue(self):
if
self.isEmpty()
:
raise IndexError('Queue empty')
self.front =
(self.front + 1) % self.maxCount
x =
self.data[self.front]
self.count -= 1
return x
def peek(self):
if self.isEmpty():
raise IndexError('Queue empty')
return
self.data[(self.front+1)% self.maxCount]
def solution(x):
return 0
🔎 Priority Queue
1) Priority Queue란
Queue가 FIFO 방식을 따르지 않고 원소들의 우선순위에 따라 Queue에서 빠져나오는 방식
2) Priority Queue의 활용
- 운영체제의 CPU 스케줄러 구현
- 현재 실행할 수 있는 작업들 중 가장 우선순위가 높은 것을 골라 실행하는 알고리즘
3) Array 구현과 Linked List 구현의 차이
- Linked List : 시간복잡도 측면에서 많이 유리, enqueue()의 경우, 우선 순위에 맞게 중간에 원소를 삽입해야하므로 삽입/제거가 유연한 Linked List가 유리
- Array : 공간복잡도 측면에서 유리하나, 시간적으로 유리한 경우를 택하는 경우가 일반적이기에 Linked List가 사용됨.
4) Priority Queue 구현
class Node:
def __init__(self, item):
self.data = item
self.prev = None
self.next = None
class DoublyLinkedList:
def __init__(self):
self.nodeCount = 0
self.head = Node(None)
self.tail = Node(None)
self.head.prev = None
self.head.next = self.tail
self.tail.prev = self.head
self.tail.next = None
def __repr__(self):
if self.nodeCount == 0:
return 'LinkedList: empty'
s = ''
curr = self.head
while curr.next.next:
curr = curr.next
s += repr(curr.data)
if curr.next.next is not None:
s += ' -> '
return s
def getLength(self):
return self.nodeCount
def traverse(self):
result = []
curr = self.head
while curr.next.next:
curr = curr.next
result.append(curr.data)
return result
def reverse(self):
result = []
curr = self.tail
while curr.prev.prev:
curr = curr.prev
result.append(curr.data)
return result
def getAt(self, pos):
if pos < 0 or pos > self.nodeCount:
return None
if pos > self.nodeCount // 2:
i = 0
curr = self.tail
while i < self.nodeCount - pos + 1:
curr = curr.prev
i += 1
else:
i = 0
curr = self.head
while i < pos:
curr = curr.next
i += 1
return curr
def insertAfter(self, prev, newNode):
next = prev.next
newNode.prev = prev
newNode.next = next
prev.next = newNode
next.prev = newNode
self.nodeCount += 1
return True
def insertAt(self, pos, newNode):
if pos < 1 or pos > self.nodeCount + 1:
return False
prev = self.getAt(pos - 1)
return self.insertAfter(prev, newNode)
def popAfter(self, prev):
curr = prev.next
next = curr.next
prev.next = next
next.prev = prev
self.nodeCount -= 1
return curr.data
def popAt(self, pos):
if pos < 1 or pos > self.nodeCount:
return None
prev = self.getAt(pos - 1)
return self.popAfter(prev)
def concat(self, L):
self.tail.prev.next = L.head.next
L.head.next.prev = self.tail.prev
self.tail = L.tail
self.nodeCount += L.nodeCount
class PriorityQueue:
def __init__(self):
self.queue = DoublyLinkedList()
def size(self):
return self.queue.getLength()
def isEmpty(self):
return self.size() == 0
def enqueue(self, x):
newNode = Node(x)
curr = self.queue.head
while curr.next != self.queue.tail and newNode.data < curr.next.data :
curr = curr.next
self.queue.insertAfter(curr, newNode)
def dequeue(self):
return self.queue.popAt(self.queue.getLength())
def peek(self):
return self.queue.getAt(self.queue.getLength()).data
def solution(x):
return 0
🔎 Binary Tree
1) Tree란
정점(Node)와 간선(edge)를 이용하여 데이터의 배치 형태를 추상화한 자료 구조
2) Binary Tree란
각각의 Node가 최대 두 개의 Child Node를 가지는 Tree
3) 연산의 정의
- size() : 현재 트리에 포함되어 있는 노드의 수를 구함
- depth() : 현재 트리의 깊이 혹은 높이를 구함
- 순회 (traversal)
- DFS (Depth First Traversal)
- in-order
- pre-order
- post-order
- BFS (Breadth First Traversal)
4) Traversal - DFS
- 중위 순회 (In-order Traversal)
# 순회의 순서 (1) Left subtree (2) Root (자기 자신) (3) Right subtree - 전위 순회 (Pre-order Traversal)
# 순회의 순서 (1) Root (자기 자신) (2) Left subtree (3) Right subtree - 중위 순회 (In-order Traversal)
# 순회의 순서 (1) Left subtree (2) Right subtree (3) Root (자기 자신)
4) Traversal - BFS
-
원칙
- Level이 낮은 Node를 우선으로 방문
- 동일한 Level의 Node들 사이의 경우,
- Parent Node의 방문 순서에 따라 방문
- Left Child Node를 Right Child Node보다 먼저 방문
-
알고리즘
- 초기화
- 빈 트리가 아니면, root node를 queue에 추가 (enqueu)
- queue가 비어있지 않은 동안
- node <- queue에서 원소 추출 (dequeue)
- node를 방문
- node의 left, right child를 q에 추가
🔎 Binary Search Tree
1) Binary Search Tree란
- 모든 노드에 대해서, 아래 성질을 만족하는 Binary Tree
- 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작음
- 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큼
(중복된 원소는 없다고 가정)
2) 연산의 정의
- insert() : 트리에 주어진 데이터 원소를 추가
- remove() : 특정 원소를 트리로부터 삭제
- lookup() : 특정 원소를 검색 (탐색)
- inorder() : 키의 순서대로 데이터 원소들을 나열
- min(), max() : 최소 키, 최대 키를 가지는 원소를 각각 탐색
3) Binary Search Tree의 추상적 자료 구조
- 각 노드는 key-value 쌍으로 표현
- 키를 이용해서 검색가능
- 복잡한 데이터 레코드로 확장 가능
- key : number, value : name
4) 장단점
장점 : 원소의 추가, 삭제가 용이
단점 : 공간 소요가 크다.
/+ 평균적으로 O(log N)의 탐색 복잡도를 가짐
5) remove() 알고리즘
- Key를 이용해서 노드를 찾는다.
- 해당 키의 노드가 없으면, 삭제하지 않는다.
- 찾은 노드의 부모 노드도 알아야한다.
- 찾은 노드를 제거하고도 Binary Search Tree의 성질을 유지하도록 구조를 정리한다.
- Binary Search Tree 구조 유지
삭제되는 노드가
1. leaf 노드인 경우 (not child)
-> 노드를 없앰
2. 자식을 하나 가지고 있는 경우
-> 노드를 없애고 그 자리에 자식을 대신 배치
3. 자식을 둘 가지고 있는 경우
-> 삭제되는 노드보다 바로 다음으로 큰 Key를 가진 노드를 찾아,
그 노드를 삭제되는 노드 자리에 배치하고 이 노드를 대신 삭제🔎 Heap
1) Heap이란
Binary Tree의 한 종류
1. Complete Binary Tree이여야 함
2. Root Node가 언제나 Max 혹은 Min 값을 가짐
2) Heap vs Binary Search Tree
- 원소들이 원전히 크기 순으로 정렬되어 있는가?
Binary Search Tree(O), Heap(X)
- 특정 키 값을 가지는 원소를 빠르게 검색할 수 있는가?
Binary Search Tree(O), Heap(X)
- 부가의 제약 조건은 어떤 것인가?
Heap은 Binary Search Tree에 비해 Complete Binary Tree여야한다는 제약 조건을 가지고 있다.
3) Heap의 장점
- Complete Binary Tree 이기에 최대 depth는 log(n)+1로 정해짐
=> 삽입/삭제의 시간복잡도가 O(log N)
- 트리의 표현 상 이점
=> 규칙에 따라 노드에 번호를 매기면, 번호 순서로 이루어진 선형 배열에 트리를 표현할 수 있다. + 삽입/삭제는 마지막 원소에서만 일어남
4) Heap의 응용
- Priority Queue ( 삽입/삭제 -> O(log N) )
- Heap Sort ( O(Nlog N) )
✍ 어려웠던 내용 & 새로 알게 된 내용
데이터 엔지니어를 꿈꾸는 거북이, 한걸음 한걸음