큐(Queue)
- 자료를 보관할 수 있는 선형 구조
- 선입선출(FIFO) 구조로 enqueue 연산과 dequeue 연산 존재
- size, isEmpty, enqueue는 스택의 메소드와 같고, dequeue와 peek만 다름
배열을 이용하여 구현
- Python 리스트와 메서드 이용
class Queue:
def __init__(self):
self.data = []
# 큐의 원소의 수
def size(self):
return len(self.data)
# 큐가 비어 있는지 판단
def isEmpty(self):
return self.size() == 0
# 데이터 원소 추가
def enqueue(self, item):
self.data.append(item)
# 가장 앞 데이터 원소 제거/반환
def dequeue(self):
return self.data.pop(0)
# 가장 앞 데이터 원소 반환
def peek(self):
return self.data[0]
배열로 구현한 큐의 연산 복잡도
연산 | 복잡도 |
size() | O(1) |
isEmpty() | O(1) |
enqueue() | O(1) |
dequeue() | O(n) |
peek() | O(1) |
연결 리스트를 이용하여 구현
- 2일 차에 구현했던 양방향 연결 리스트 이용
from doublylinkedlist import Node, DoublyLinkedList
class LinkedListQueue:
def __init__(self):
self.data = DoublyLinkedList()
# 큐의 원소의 수
def size(self):
return self.data.getLength()
# 큐가 비어 있는지 판단
def isEmpty(self):
return self.size() == 0
# 데이터 원소 추가
def enqueue(self, item):
node = Node(item)
self.data.insertAt(self.size() + 1, node)
# 가장 앞 데이터 원소 제거/반환
def dequeue(self):
return self.data.popAt(1)
# 가장 앞 데이터 원소 반환
def peek(self):
return self.data.getAt(1).data
큐의 활용
- 자료 생성 작업과 이용하는 작업이 비동기적으로 일어나는 경우 (ex. Producer - Producer)
- 자료 생성 작업이 여러 곳에서 일어나는 경우 (ex. Producer1/2 - Consumer)
- 자료 이용 작업이 여러 곳에서 일어나는 경우 (ex. Producer - Consumer1/2)
- 자료 생성 작업과 이용하는 작업이 모두 여러 곳에서 일어나는 경우 (ex. Producer1/2 - Consumer1/2)
- 자료를 처리하여 새로운 자료를 생성하고, 그 자료를 또 처리해야 하는 작업의 경우 (다시 enqueue)
환형 큐(Circular Queues)
- 정해진 개수의 저장 공간을 돌려가며 이용
- 데이터를 꺼내는 곳을 front, 데이터가 입력되는 곳을 rear로 지정
- 큐 길이를 기억하여 큐가 가득찼는지, 비어있는지 판단
배열을 이용하여 구현
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 isFull(self):
return self.count == self.maxCount
# 큐가 비어 있는지 판단
def isEmpty(self):
return self.count == 0
# 데이터 원소 추가
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]
우선순위 큐(Priority Queues)
- 큐가 FIFO 방식을 따르지 않고, 원소의 우선순위에 따라 큐에서 빠져나오는 방식
- 예시) 작은 수가 우선순위↑ : 6 7 3 2 순서로 Enqueue, 그러나 2 3 6 7 순서로 Dequeue
- 운영체제의 CPU 스케줄러에 활용
우선순위 큐의 구현
- Enqueue 할 때, 우선순위 순서를 유지하도록 조정하거나 Dequeue 할 때, 우선순위 높은 것을 선택
- 우선순위의 순서를 유지하도록 하는게 더 효율적인 방법
- 선형 배열과 연결 리스트를 활용 가능
- 시간적으로는 원소 삽입이 자유로운 연결 리스트가 유리, 그러나 공간적으로는 선형 배열이 유리
연결 리스트를 이용하여 구현
- enqueue 메서드 말고는 모두 일반 큐와 같으므로 enqueue만 작성
- 작은 숫자가 우선순위가 높다고 가정한 코드
- 단, dequeue는 tail 앞의 원소를 dequeue하므로 내림차순으로 표시되야 함
from doublylinkedlist import Node, DoublyLinkedList
class PriorityQueue:
def __init__(self, x):
self.queue = DoublyLinkedList()
def enqueue(self, x):
newNode = Node(x)
curr = self.queue.head
while curr.next != self.queue.tail and curr.next.data > x
curr = curr.next
self.queue.insertAt(curr, newNode)
트리(Trees)
- 정점(node)과 간선(Edge)을 이용하여 데이터의 배치 형태를 추상화한 자료구조
이진 트리(Binary Tree)
- 모든 노드의 차수가 2 이하인 트리(위의 그림도 이진 트리)
- 재귀적으로 정의 가능, 빈 트리 or 루트 노드 + 왼쪽 서브트리 + 오른쪽 서브트리
포화 이진 트리(Full Binary Tree)
- 모든 레벨에서 노드가 모두 채워져 있는 이진 트리
- 높이가 k이고, 노드의 개수가 2^k - 1인 이진 트리
완전 이진 트리(Complete Binary Tree)
- 높이가 k인 완전 이진 트리는 다음을 만족함
레벨 k - 2까지는 모든 노드가 2개의 자식을 가진 포화 이진 트리
레벨 k - 1에서는 왼쪽부터 노드가 순차적으로 채워져 있는 이진 트리
이진 트리(Binary Trees)
이진 트리의 구현
- 트리의 재귀적인 성질을 이용하여 메서드 구현
- 깊이 우선 순회 : 중위 순회, 전위 순회, 후위 순회
class Node:
def __init__(self, item):
self.data = item
self.left = None
self.right = None
def size(self):
l = self.left.size() if self.left else 0
r = self.right.size() if self.right else 0
return l + r + 1
def depth(self):
l = self.left.depth() if self.left else 0
r = self.right.size() if self.right else 0
if l > r:
return l + 1
else:
return r + 1
def inorder(self):
traversal = []
if self.left:
traversal += self.left.inorder()
traversal.append(self.data)
if self.right:
traversal += self.right.inorder()
return traversal
def preorder(self):
traversal = []
traversal.append(self.data)
if self.left:
traversal += self.left.inorder()
if self.right:
traversal += self.right.inorder()
return traversal
def postorder(self):
traversal = []
if self.left:
traversal += self.left.inorder()
if self.right:
traversal += self.right.inorder()
traversal.append(self.data)
return traversal
class BinaryTree:
def __init__(self, r):
self.root = r
# 트리의 노드 수
def size(self):
if self.root:
return self.root.size()
else:
return 0
# 트리의 깊이
def depth(self):
if self.root:
return self.root.depth()
else:
return 0
# 중위 순회
def inorder(self):
if self.root:
return self.root.inorder()
else:
return []
# 전위 순회
def preorder(self):
if self.root:
return self.root.preorder()
else:
return []
# 후위 순회
def postorder(self):
if self.root:
return self.root.postorder()
else:
return []
이진 트리 - 넓이 우선 순회(Breadth First Traversal)
- 수준(Level)이 낮은 노드를 우선으로 방문
- 수준이 같다면 부모 노드의 방문 순서에 따라 방문 및 왼쪽 자식 노드 먼저 방문
알고리즘
- 큐를 활용해서 해당 노드의 자식들을 큐에 저장
- dequeue하여 큐에 저장했던 노드 순회
- 큐가 비어있으면 순회가 끝난 것
알고리즘 구현
- 리스트 traversal, 큐 q 초기화
- 빈 트리가 아니면, root node를 q에 enqueue
- q가 비어있지 않은 동안, dequeue / node 방문 / node의 자식들을 q에 추가
- q가 비어있으면 종료
def bft(self):
q = ArrayQueue()
traversal = []
if self.size() != 0:
q.enqueue(self.root)
while not q.isEmpty():
node = q.dequeue()
traversal.append(node.data)
if node.left:
q.enqueue(node.left)
if node.right:
q.enqueue(node.right)
return traversal
이진 탐색 트리(Binary Search Trees) (1), (2)
- 모든 노드에 대해 다음을 만족하는 이진 트리
왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작음
오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큼
중복되는 데이터는 없다고 가정
- 장점 : 데이터 원소의 추가, 삭제가 용이
- 단점 : 공간 소요가 큼, 트리가 한 쪽으로 치우쳐져 있는 경우 시간적 효율성을 얻지 못함
- AVL Tree, Red-black Tree : 높이의 균형을 유지함으로써 O(log n)의 탐색 복잡도 보장
이진 탐색 트리 삭제
- 말단(leaf) 노드 삭제, 만약 루트 노드라면 트리가 없어짐
- 자식이 하나인 노드 삭제
- 자식이 둘인 노드의 삭제
이진 탐색 트리 구현
class Node:
def __init__(self, key, data):
self.key = key
self.data = data
self.left = None
self.right = None
# 자식의 수 반환
def countChildren(self):
count = 0
if self.left:
count += 1
if self.right:
count += 1
return count
def insert(self, key, data):
if key < self.key:
if self.left:
self.left.insert(key, data)
else:
self.left = Node(key, data)
elif key > self.key:
if self.right:
self.right.insert(key, data)
else:
self.right = Node(key, data)
else:
raise KeyError()
def lookup(self, key, parent=None):
if key < self.key:
if self.left:
return self.left.lookup(key, self)
else:
return None, None
elif key > self.key:
if self.right:
return self.right.lookup(key, self)
else:
return None, None
else:
return self, parent
def inorder(self):
traversal = []
if self.left:
traversal += self.left.inorder()
traversal.append(self)
if self.right:
traversal += self.right.inorder()
return traversal
def min(self):
if self.left:
return self.left.min()
else:
return self
class BinarySearchTrees:
def __init__(self):
self.root = None
# 삽입
def insert(self, key, data):
if self.root:
self.root.insert(key, data)
else:
self.root = Node(key, data)
# 삭제
def remove(self, key):
node, parent = self.lookup(key)
if node:
nChildren = node.countChildren()
# The simplest case of no children
if nChildren == 0:
if parent:
if parent.left == node:
parent.left = None
else:
parent.right = None
else:
self.root = None
# When the node has only one child
elif nChildren == 1:
if node.left:
tmp = node.left
else:
tmp = node.right
if parent:
if parent.left == node:
parent.left = tmp
else:
parent.right = tmp
else:
self.root = tmp
# When the node has both left and right children
else:
parent = node
successor = node.right
while successor.left:
successor = successor.left
_, parent = self.lookup(successor.key)
node.key = successor.key
node.data = successor.data
if parent.left == successor:
parent.left = successor.right
else:
parent.right = successor.right
return True
else:
return False
# 특정 키의 노드 탐색
def lookup(self, key):
if self.root:
return self.root.lookup(key)
else:
return None, None
# 중위 순회
def inorder(self):
if self.root:
return self.root.inorder()
else:
return []
# 최소키 탐색
def min(self):
def min(self):
if self.root:
return self.root.min()
else:
return None
힙(Heaps) (1), (2)
- 루트 노드가 언제나 최댓값(최대 힙) 또는 최솟값(최소 힙)을 가지며 완전 이진 트리
이진 탐색 트리와의 비교
- 원소들은 완전히 크기 순으로 정렬되어 있는가? => 이진 탐색 트리 (O), 힙 (X)
- 특정 키 값을 가지는 원소를 빠르게 검색할 수 있는가? => 이진 탐색 트리 (O), 힙 (X)
- 부가의 제약 조건은 어떤 것인가? => 힙은 완전 이진 트리!
최대/최소 힙의 응용
- 우선 순위 큐 : Enqueue할 때 느슨한 정렬을 이루도록 하고, Dqueue할 때 최댓값을 순서대로 추출
- 힙 정렬 : 정렬되지 않은 원소를 힙에 삽입 및 힙이 빌 때까지 하나씩 삭제 => 삭제된 순서가 정렬 순서, O(nlog n)
def heapsort(unsorted):
H = maxHeap()
for item in unsorted:
H.insert(item)
sorted = []
d = H.remove()
while d:
sorted.append(d)
d = H.remove()
return sorted
배열을 이용한 이진 트리의 표현
- 노드 번호 m 기준, 왼쪽 자식의 번호 - 2m, 오른쪽 자식 번호 - 2m + 1, 부모 노드 번호 - m // 2
- "완전 이진 트리"이므로 노드의 추가/삭제는 마지막 노드에서만 이루어짐
- 원소 삽입 복잡도 : O(log n)
- 원소 삭제 복잡도 : O(log n)
class MaxHeap:
def __init__(self):
self.data = [None]
def insert(self, item):
self.data.append(item)
i = len(self.data) - 1
while i != 1 and self.data[i // 2] < self.data[i]:
self.data[i // 2], self.data[i] = self.data[i], self.data[i // 2]
i = i // 2
def maxHeapify(self, i):
left = 2 * i
right = 2 * i + 1
smallest = i
if len(self.data) > left and self.data[left] > self.data[smallest]:
smallest = left
if len(self.data) > right and self.data[right] > self.data[smallest]:
smallest = right
if smallest != i:
self.data[i], self.data[smallest] = self.data[smallest], self.data[i]
self.maxHeapify(smallest)
def remove(self):
if len(self.data) > 1:
self.data[1], self.data[-1] = self.data[-1], self.data[1]
data = self.data.pop(-1)
self.maxHeapify(1)
else:
data = None
return data
Python에서 두 변수의 값 바꾸기
a = 3; b = 5
a, b = b = a
결론
느낀 점
- 어제와 비교했을 때, 공부양은 비교적 적었지만 실습 부분에서 사소한 오류를 잡는데 시간이 오래 걸림
- 확실히 자료구조나 알고리즘은 이해가 기반된 학습이 필요하다고 느낌
어려웠던 점
- 이진 탐색 트리의 삭제 부분에서 모든 상황을 고려하기가 어렵다고 생각함
- 추가적으로 AVL 트리, Red-black Tree에 대해 공부해보면 좋을 것 같음
참고링크
[자료구조] 원형 큐(Circular Queue) 개념 및 코드
나무위키 : 트리(그래프)
https://namu.wiki/w/%ED%8A%B8%EB%A6%AC%28%EA%B7%B8%EB%9E%98%ED%94%84%29
'[프로그래머스] 데이터 엔지니어링 데브코스 3기 > TIL(Today I Learn)' 카테고리의 다른 글
[TIL - 6일 차] 데이터 엔지니어링 : 파이썬으로 웹 데이터를 크롤하고 분석하기 (1) (2) | 2024.04.01 |
---|---|
[TIL - 5일 차] 데이터 엔지니어링 : 자료구조/알고리즘 풀기 (5) (0) | 2024.03.29 |
[TIL - 4일 차] 데이터 엔지니어링 : 자료구조/알고리즘 풀기 (4) (0) | 2024.03.28 |
[TIL - 2일 차] 데이터 엔지니어링 : 자료구조/알고리즘 풀기 (2) (0) | 2024.03.26 |
[TIL - 1일 차] 데이터 엔지니어링 : 자료구조/알고리즘 풀기 (1) (0) | 2024.03.25 |