오늘의 학습 주제
- 큐(Queues)
- 환형 큐(Circular Queue)
- 우선순위 큐(Priority Queues)
- 트리(Trees)
- 이진 트리(Binary Trees)
- 이진 탐색 트리(Binary Search Trees)
- 힙(Heaps)
1.큐(Queues)
큐(Queue)
자료를 보관할 수 있는 (선형) 구조
단, 넣을 때에는 한 쪽 끝에서 밀어 넣어야 하고
인큐연산
꺼낼 때에는 반대 쪽에서 뽑아 꺼내야 하는 제약이 있음
디큐연산
선입선출(FIFO) 특징을 가지는 선형 자료구조
Q = Queue()
Q.enqueue(A)
Q.enqueue(B)
r1 = Q.dequeue() -> A
r2 = Q.dequeue() -> B
큐의 추상적 자료구조 구현
(1) 배열 이용 -> python 리스트, 메서드 이용
(2) 연결 리스트 이용 -> 양방향 연결 리스트 이용
연산의 정의
size() : 현재 큐에 들어 있는 데이터 원소의 수를 구함
isEmpty() : 현재 큐가 비어 있는지를 판단
enqueue(x) : 데이터 원소 x를 큐에 추가 push
dequeue() : 큐의 맨 앞에 저장된 데이터 원소를 제거 (또한, 반환) pop
peek() : 큐의 맨 앞에 저장된 데이터 원소를 반환 (제거하지 않음)
배열로 구현한 큐
class ArrayQueu:
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(), isEmpty(), enqueue(), peek() -> O(1)
dequeue() -> O(n)
이중 연결 리스트로 큐를 구현
dequeue() 연산은 배열로 구현하기에는 효율적이지 않다. 연결 리스트로 구현 추천.
연산의 복잡도에 대해 고려할 것. 이중 연결 리스트 뿐만 아니라 연결 리스트로 구현해 보는 것도 추천.
pythonds.basic.queue 라이브를 이용하는 방법
환형 큐(Circular Queue)
큐(Queue)의 활용
자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로 일어나는 경우
자료를 생성하는 작업이 여러 곳에서 일어나는 경우
자료를 이용하는 작업이 여러 곳에서 일어나는 경우
자료를 생성하는 작업과 그 자료를 이용하는 작업이 양쪽 다 여러 곳에서 일어나는 경우
자료를 처리하여 새로운 자료를 생성하고, 나중에 그 자료를 또 처리해야 하는 작업의 경우
환형 큐 : 정해진 개수의 저장 공간을 빙 둘려가며 이용
Q.enqueue(A)
Q.enquque(B)
Q.enquque(C)
r1 = Q.dequeue() A
Q.enqueue(D)
r2 = Q.dequeqe() B
rear(넣는 포인터) / front(꺼내는 포인터)
큐가 가득 차면? 더이상 원소를 넣을 수 없음 (큐 길이를 기억하고 있어야)
환형 큐의 추상적 자료구조 구현
연산의 정의
isFull() - 큐에 데이터 원소가 꽉 차 있는지를 판단
배열로 구현한 환형 큐
정해진 길이 n(예에서는 6)의 리스트를 확보해 두고
Q.enqueue(A) rear가 A를 가리킴
Q.enqueue(B) rear가 B를 가리킴.
r1 = Q.dequeue() front가 A를 가리킴
r2 = Q.dequeue() front가 B를 가리킴
front와 rear를 적절히 계산하여 배열을 환형으로 재활용
class CircularQueue:
definit(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
우선순위 큐(Priority Queues)
큐가 FIFO 방식을 따르지 않고, 원소들의 우선순위에 따라 큐에서 빠져나오는 방식
서로 다른 두 가지 방식이 가능할 듯:
(1) enqueue 할 때 우선순위 순서 유지
(2) dequeue 할 때 우선순위 높은 것을 선택
어느 것이 더 유리할까? 1번이 유리
서로 다른 두 가지 재료를 이용할 수 있음
(1) 선형 배열 이용
(2) 연결 리스트 이용
어느 것이 더 유리할까? 시간적으로는 2번이 유리.
우선순위 큐의 초기화
양방향 연결 리스트를 이용하여 빈 큐를 초기화
끝을 만나지 않았을 조건 and 우선 순위 조건
양방향 연결 리스트의 getAt() 메서드를 이용하지 않음!
트리(Trees)
정점(node)과 간선(edge)을 이용하여 데이터의 배치 형태를 추상화한 자료 구조
포화 이진 트리(Full Binary Tree)
모든 레벨에서 노드들이 모두 채워져 있는 이진 트리
(높이가 k이고 노드의 개수가 2^4-1인 이진 트리)
완전 이진 트리(Complete Binary Tree)
높이 k인 완전 이진 트리
레벨 k-2 까지는 모든 노드가 2개의 자식을 가진 포화 이진 트리
레벨 k-1 에서는 왼쪽부터 노드가 순차적으로 채워져 있는 트리
이진 트리(Binary Trees)
이진 트리의 추상적 자료구조
연산의 정의
size() : 현재 트리에 포함되어 있는 노드의 수를 구함
depth() : 현재 트리의 깊이 (또는 높이)를 구함
순회(traversal)
이진 트리의 구현 - 노드(Node)
data
left child
right child
class Node:
def init(self, item):
self.data = item
self.left = None
self.right = None
root
class BinaryTree:
def init(self, r):
self.root = r
class Node:
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
class BinaryTree:
def size(self):
if self.root:
return self.root.size()
else:
return 0
depth() : 재귀적인 방법으로 쉽게 구할 수 있음!
class node:
def depth(self):
if l = self.left.size
class BinaryTree:
def depth(self):
if
이진 트리의 순회(Traversal)
깊이 우선 순회(depth first traversal)
중위 순회
순회의 순서
1. left subtree
2. 자기자신
3. right subtree
class Node:
defe inorder(self):
traversal = []
if self.left:
traversal += self.left.inorder()
traversal.append(self.data)
if self.right:
traversal += self.right.inorder()
return traversal
class BinaryTree:
def inorder(self):
if self.root:
return self.root.inorder()
else:
return[]
전위 순회
순회의 순서
1. 자기자신
2. left subtree
3. right subtree
후위 순회
순회의 순서
1. left subtree
2. right subtree
3. 자기자신
넓이 우선 순회(bfs; breadth first traversal)
원칙 : 수준(level)이 낮은 노드를 우선으로 방문
같은 수준의 노드들 사이에는, 부모 노드의 방문 순서에 따라 방문
재귀적 방법이 적합한가? 그렇지 않다.
넓이 우선 순회 알고리즘 설계
queue를 이용
넓이 우선 순회 알고리즘 구현
class BinaryTree:
def bft(self):
1.(초기화) traversal <- 빈 리스트, <- 빈 큐
2. 빈 트리가 아니면. root node 를 q 에 추가 (enqueue)
3. q가 비어 있지 않은 동안
3.1 node <- q에서 원소를 추출 (dequeue)
3.2 node 를 방문 = traverl에 node를 append
3.3 node의 왼쪽, 오른쪽 자식 (있으면) 들을 q에 추가
4. q가 빈 큐가 되면 모든 노드 방문 완료
이진 탐색 트리(Binary Search Trees)
모든 노드에 대해서
왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고
오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰
성질을 만족하는 이진트리
이진 탐색 트리를 이용한 데이터 검색
(정렬된) 배열을 이용한 이진 탐색과 비교
(장점) 데이터 원소의 추가, 삭제가 용이
(단점) 공간 소요가 큼
항상 O(logn)의 탐색 복잡도?
데이터 표현 - 각 노드는 (key, value)의 쌍으로
키를 이용해서 검색 가능
보다 복잡한 데이터 레코드로 확장 가능
이진 탐색 트리의 추상적 자료구조
연산의 정의
insert(key, data) - 트리에 주어진 데이터 원소를 추가
remove(key) - 특정 원소를 트리로부터 삭제
lookup(key) - 특정 원소를 검색
inorder() - 키의 순서대로 데이터 원소를 나열
min(), max() - 최소 키, 최대 키를 가지는 원소를 각각 탐색
이진 탐색 트리에 원소 삽입
class Node:
def init(self, key, data):
self.key = key
self.data = data
self.left = None
self.right = None
in-order traversal
class Node:
def inorder(self):
traversal = []
if self.left:
traversal += self.left.inorder()
traversal.append(self)
if self.right:
traversal += self.right.inorder()
return traversal
class BinSearchTree:
def inorder(self):
if self.root:
return self.root.inorder()
else:
return []
class BinSearchTree:
def min(self):
if self.root:
return self.root.min()
else:
return None
class Node:
def min(self):
if self.left:
return self.left.min()
else:
return self
max()
min()과 완전히 대칭
lookup()
입력 인자 : 찾으려는 대상 키
리턴 : 찾은 노드와, 그것의 부모 노드
class BinSearchTree:
def BinSearchTree:
def lookup(self, key):
if self.root:
return self.root.lookup(key)
else:
return None, None
class Node:
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:
return self.right.lookup(key, self)
else:
return None, None
else:
return self, parent
코드 구현 - insert()
입력 인자:
키, 데이터 원소
리턴:
없음
class BinSearchTree:
def insert(self, key, data):
if self.root:
self.root.insert(key, data)
else:
self.root = Node(key, data)
class Node:
def insert(self, key, data):
if key<self.key:
elif key> self.key:
raaise KeyError('...')
이진 탐색 트리(Binery Search Tree)
힙(Heaps)
