큐(Queue)
- 자료를 보관할 수 있는 (선형) 구조
- 단, 넣을 때에는 한쪽 끝에서 밀어 넣어야 하고, 꺼낼 때에는 반대쪽에서 뽑아 꺼내야 함
- FIFO(First-in First-out)
- 연산
1) size() : 현재 큐에 들어있는 데이터 원소 수
2) isEmpty() : 현재 큐가 비어있는지
3) enqueue(x) : 데이터 원소 x를 큐에 추가
4) dequeue() : 큐의 맨 앞에 저장된 데이터 원소를 제거(&반환)
5) peek() : 큐의 맨 앞 데이터 원소를 반환(제거하지 않음)
- 큐의 추상적 자료구조 구현- 배열(array)을 이용해 구현
# 1. 배열(array)을 이용해 구현 - python 리스트와 메서드들을 이용
class ArrayQueue:
# 큐의 크기를 리턴
def size(self):
return len(self.data)
# 큐가 비어 있는지 판단
def isEmpty(self):
return self.size() == 0
# 큐의 맨 앞 원소 반환
def peek(self):
return self.data[0]| 연산 | (배열로 구현한 큐) 복잡도 |
| size() | O(1) |
| isEmpty() | O(1) |
| enqueue() | O(1) |
| dequeue() | O(n) |
| peek() | O(1) |
- 배열로 큐를 구현하면, 배열의 맨 앞 원소를 꺼낼때 뒤 원소들을 한칸씩 당겨야하는 비효율성이 발생함
- 양방향 연결 리스트를 이용해 구현
# 2. 양방향 연결 리스트를 이용해 구현
class LinkedListQueue:
def __init__(self):
self.data = DoublyLinkedList()
# 사이즈 확인
def size(self):
return self.data.getLength()
# 비어있는지 확인
def isEmpth(self):
return self.data.getLength() == 0
# 원소 추가
def enqueue(self,item):
node = Node(item)
self.data.insertAt(self.data.nodeCount+1, node)
# 원소 삭제
def dequeue(self):
return self.data.popAt(1)
# 맨 위 원소 확인
def peek(self):
return self.data.getAt(1).data| 연산 | (양방향 연결 리스트로 구현한 큐) 복잡도 |
| size() | O(1) |
| isEmpty() | O(1) |
| enqueue() | O(1) |
| dequeue() | O(1) |
| peek() | O(1) |
큐의 활용
- 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적(asynchronously)으로 일어나는 경우
- 자료를 생성하는 작업이 여러 곳에서 일어나는 경우
- 자료를 이용하는 작업이 여러 곳에서 일어나는 경우
- 자료 생성/이용 모두 여러 곳에서 일어나는 경우(운영체제에서 비일비재하게 이용)
- 자료를 처리해 새로운 자료를 생성하고, 나중에 그 자료를 또 처리해야 하는 작업의 경우
환형 큐(Circular Queue)
- 정해진 개수의 저장 공간을 빙 돌려가며 이용함
- 큐가 가득 차면 더이상 원소를 넣을 수 없음
- 연산
1) size() : 현재 큐에 들어 있는 데이터 원소의 수를 구함
2) isEmpty() : 현재 큐가 비어있는지 판단
3) isFull() : 큐에 데이터 원소가 꽉 차 있는지 판단 → 선형 큐와의 차이
4) enqueue(x) : 데이터 원소 x를 큐에 추가
5) dequeue() : 큐의 맨 앞에 저장된 데이터 원소를 제거(&반환)
6) peek() : 큐의 맨 앞에 저장된 데이터 원소를 반환(제거하지 않음)
- 환형 큐의 추상적 자료구조 구현
- 배열로 구현한 환형 큐
# 1. 배열로 구현한 환형 큐
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]
우선순위 큐(Priority Queue)
- 우선순위에 따라 데이터가 꺼내지는 큐
- FIFO를 따르지 않고 우선순위가 정해져 있음
- 두 가지 방식으로 구현 가능함
1) Enqueue 때, 우선순위 순서를 유지하도록 → 더 유리함. 큐에 우선순위를 따라 넣었기 때문에 다 확인할 필요 X
2) Dequeue 때, 우선순위 높은 것을 선택하도록 - 우선순위 큐의 추상적 자료구조 구현
- 선형 배열 이용
- 양방향 연결 리스트 이용
# 2. 양방향 연결 리스트를 이용한 우선순위 큐 구현
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.data != None and x < 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 size(self):
return self.queue.getLength()
# 비어있는지 확인
def isEmpty(self):
return self.size() == 0
트리(Trees)
- 정점(node)과 간선(edge)을 이용해 데이터의 배치 형태를 추상화한 자료 구조
- 설명
- 나무와 같이 뿌리(root)가 있고, 이파리(leaf)가 있음
- 루트 노드를 가장 첫 노드로 보고, 리프 노드는 더이상 자식 노드가 없는 끝 노드를 말함
- 루트에서부터 현재 노드까지의 길이를 수준(level)이라고 함
- 높이(또는 깊이. height or depth)는 최대 수준 + 1
- 서브트리(subtree)
- 트리 중 일부분
- 노드의 차수(degree) = 자식(서브트리)의 수
- 여러 형태의 트리
- 이진 트리(Binary tree) : 모든 노드의 차수가 2 이하인 트리
- 포화 이진 트리(Full Binary tree) : 모든 레벨에서 노드들이 모두 채워져 있는 이진 트리(높이 k, 노드 개수 2^k-1)
- 완전 이진 트리(Complete Binary tree) : 레벨 k-2까지는 모든 노드가 2개의 자식을 가진 포화 이진 트리. 레벨 k-1에서는 왼쪽부터 노드가 순차적으로 다 채워져 있으면 완전 이진 트리
이진 트리(Binary Trees)
- 모든 노드의 차수가 2 이하인 트리
- 연산
1) size() : 현재 트리에 포함되어 있는 노드의 수
2) depth() : 현재 트리의 깊이(또는 높이)를 구함
3) traversal() : 순회
- 이진 트리의 순회 (traversal)
1) 깊이 우선 순회 (depth first traversal) - 재귀 적합
- 중위 순회 (in-order traversal) : left, 자신, right
- 전위 순회 (pre-order traversal) : 자신, left, right
- 후위 순회 (post-order traversal) : left, right, 자신
2) 넓이 우선 순회 (breadth first traversal) - 재귀 부적합
- 수준이 낮은 노드를 우선 방문
- 같은 수준의 노드들을 왼쪽부터 순서대로 방문
- 따라서 한 부모 노드를 방문할때 나중에 방문할 그들의 자식 노드들을 기록해 두어야함 → 큐 사용!
- 이진 트리의 구현
- Node(Data, Left child, Right child)
- binaryTree(root)
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.depth() if self.right else 0
return max(l,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 []
## 너비 우선 순회
def bft(self):
traversal = []
q = ArrayQueue()
if self.root:
q.enqueue(self.root)
while q.size() != 0:
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)
- 모든 노드에 대해 다음과 같은 성질을 만족하는 이진 트리 (중복되는 원소는 없다고 가정)
- 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고
- 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰
- 이진 탐색 트리 vs (정렬된) 배열을 이용한 이진 탐색
(장점) 데이터 원소의 추가, 삭제가 용이
(단점) 공간 소요가 큼 - 왼쪽, 오른쪽 자식을 언제나 기록해둬야함
- 연산
1) insert(key, data) : 트리에 주어진 데이터 원소를 추가
2) remove(key) : 특정 원소를 트리로부터 삭제 - 복쟙
3) lookup(key) : 특정 원소를 검색
4) inorder() : 키의 순서대로 데이터 원소를 나열
5) min(), max() : 최소 키, 최대 키를 가지는 원소를 각각 탐색
- 이진 탐색 트리에서 원소 삭제
1) key를 이용해 노드를 찾음
- 해당 키의 노드가 없으면, 삭제할 것도 없음
- 찾은 노드의 부모 노드도 알고 있어야 함 (왜? 2번 때문)
2) 찾은 노드를 제거하고도 이진 탐색 트리 성질을 만족하도록 트리의 구조를 정리함
- 리프 노드인 경우 : 그냥 그 노드를 없앰(부모 노드 링크를 조정)
- 자식을 하나 가지고 있는 경우 : 삭제되는 노드 자리에 그 자식을 대신 배치
- 자식을 둘 가지고 있는 경우 : 삭제되는 노드보다 바로 다음 (큰) 키를 가진 노드를 대신 배치하고, 이 노드를 대신 삭제
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 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.root:
return self.root.min()
else:
return self
def max(self):
if self.root:
return self.root.max()
else:
return self
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 insert(self, key, data):
if self.key is key:
raise KeyError
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)
class BinSearchTree:
def __init__(self):
self.root = None
# 순서대로 데이터 나열
def inorder(self):
if self.root:
return self.root.inorder()
else:
return []
# 최소값
def min(self):
if self.root:
return self.root.min()
else:
return None
# 최대값
def max(self):
if self.root:
return self.root.max()
else:
return None
# 특정 원소 검색
def lookup(self, key):
if self.root:
return self.root.lookup(key)
else:
return None, 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:
# 만약 parent 가 있으면
# node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
# parent.left 또는 parent.right 를 None 으로 하여
# leaf node 였던 자식을 트리에서 끊어내어 없앱니다.
if parent:
if node == parent.right:
parent.right = None
if node == parent.left:
parent.left = None
# 만약 parent 가 없으면 (node 는 root 인 경우)
# self.root 를 None 으로 하여 빈 트리로 만듭니다.
else:
self.root = None
# When the node has only one child
elif nChildren == 1:
# 하나 있는 자식이 왼쪽인지 오른쪽인지를 판단하여
# 그 자식을 어떤 변수가 가리키도록 합니다.
if node.left:
direct = node.left
else:
direct = node.right
# 만약 parent 가 있으면
# node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
# 위에서 가리킨 자식을 대신 node 의 자리에 넣습니다.
if parent:
if node == parent.right:
parent.right = direct
else:
parent.left = direct
# 만약 parent 가 없으면 (node 는 root 인 경우)
# self.root 에 위에서 가리킨 자식을 대신 넣습니다.
else:
self.root = direct
# When the node has both left and right children
else:
parent = node
successor = node.right
# parent 는 node 를 가리키고 있고,
# successor 는 node 의 오른쪽 자식을 가리키고 있으므로
# successor 로부터 왼쪽 자식의 링크를 반복하여 따라감으로써
# 순환문이 종료할 때 successor 는 바로 다음 키를 가진 노드를,
# 그리고 parent 는 그 노드의 부모 노드를 가리키도록 찾아냅니다.
while successor.left:
parent = successor
successor = successor.left
# 삭제하려는 노드인 node 에 successor 의 key 와 data 를 대입합니다.
node.key = successor.key
node.data = successor.data
# 이제, successor 가 parent 의 왼쪽 자식인지 오른쪽 자식인지를 판단하여
# 그에 따라 parent.left 또는 parent.right 를
# successor 가 가지고 있던 (없을 수도 있지만) 자식을 가리키도록 합니다.
if successor.key is parent.left.key:
parent.left = successor.right
else:
parent.right = successor.right
return True
else:
return False
- 이진 탐색 트리가 비효율적인 경우
- 순서대로(1,2,3,4 ...) 키를 가지는 경우 → 균형이 없으면 선형 탐색과 동등한 정도의 복잡도 - 보다 나은 성능을 보이는 이진 탐색 트리들
- 높이의 균형을 유지함으로써 O(log n)의 탐색 복잡도 보장
- 삽입, 삭제 연산이 보다 복잡함
1) AVL tree
2) Red-black tree
힙(Heap)
- 완전 이진 트리
- 루트 노드가 언제나 최대 혹은 최소를 가짐(최대 힙 - 루트가 최대, 최소 힙 - 루트가 최소)
- 이진 탐색 트리와 비교해 질문할 거리
1) 원소들은 완전히 크기 순으로 정렬되어 있는가?
2) 특정 키 값을 가지는 원소를 빠르게 검색할 수 있는가?
3) 부가의 제약 조건은 어떤 것인가? - 연산 - 최대 힙
1) __init__() : 빈 최대 힙 생성
2) insert(item) : 새로운 원소 삽입
3) remove() : 최대 원소(root node)를 반환 & 삭제 - 배열을 이용한 이진 트리의 표현은 노드 번호 m을 기준으로
1) 왼쪽 자식 번호 : 2 * m
2) 오른쪽 자식 번호 : 2 * m + 1
3) 부모 노드의 번호 : m // 2
완전 이진 트리이므로, 노드의 추가/삭제는 마지막 노드에서만 이뤄짐 - 최대 힙에 원소 삽입할 때의 복잡도
- 원소 개수 n인 최대 힙에 새로운 원소를 삽입하면, 부모 노드와의 대소 비교 최대 횟수가 log n. O(log n) - 최대 힙에 원소 삭제할 때의 복잡도
- 원소 개수 n인 최대 힙에 원소를 삭제하면, 자식 노드와의 대소 비교 최대 횟수가 2* log n. O(log n)
class MaxHeap:
def __init__(self):
self.data = [None]
# 원소 삽입
def insert(self, item):
self.data.append(item)
m = len(self.data) - 1
while m > 1:
if self.data[m] > self.data[m//2]:
self.data[m], self.data[m//2] = self.data[m//2], self.data[m]
m = m // 2
else:
break
# 원소 삭제
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
# 최대 힙
def maxHeapify(self, i):
left = 2*i
right = 2*i + 1
smallest = i # 일단 자기 자신을 최솟값으로
# 자신과 왼,오 자식을 비교해 최대를 찾고, 이것을 smallest에 담음
if left < len(self.data) and self.data[left] > self.data[smallest]:
smallest = left
if right < len(self.data) and self.data[right] > self.data[smallest]:
smallest = right
# 만약 최대 값이 자기 자신이 아니면 현재 노드 i와 최대 노드 smallest 값 바꿈
if smallest != i:
self.data[smallest], self.data[i] = self.data[i], self.data[smallest]
# 재귀적으로 최대 힙 성질을 만족할 때까지 트리 정리
self.maxHeapify(smallest)
- 최대/최소 힙의 응용
1) 우선순위 큐 (양방향 연결 리스트를 이용한 구현과 효율성을 비교해보렴)
2) 힙 정렬. O(nlogn) - 힙 정렬의 코드 구현
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'dev course - DE > TIL' 카테고리의 다른 글
| [데브코스] TIL 6일차 (0) | 2024.04.01 |
|---|---|
| [데브코스] TIL 5일차 (1) | 2024.03.29 |
| [데브코스] TIL 4일차 (0) | 2024.03.28 |
| [데브코스] TIL 2일차 (0) | 2024.03.26 |
| [데브코스] TIL 1일차 (0) | 2024.03.25 |
