수식의 후위 표기법
- 중위 표기법(infix notation): 연산자가 피연산자들의 사이에 위치
(A + B) * (C + D)- 후위 표기법(postfix notation): 연산자가 피연산자들의 뒤에 위치
괄호가 필요하지 않으며 앞에서부터 순서대로 연산 가능
AB + CD + *- 스택의 응용 1 - 중위 표현식을 후위 표현식으로 변환하기
1. 중위 표현식을 차례대로 검사하여 피연산자일 경우 그대로 쓰고,
연산자일경우 스택에 push한다.
2. 연산자를 스택에 push할 때, 현재 스택의 맨 위에 있는 연산자와 비교하여 스택에 있는 연산자의 우선순위가 더 높다면 pop하여 쓴다. 그렇지 않을 경우 스택에 push한다.
동일한 우선순위일 때는 스택에 있는 연산자를 pop하여 쓴다.
2 - 1. 괄호가 있는 표현식의 경우, 여는 괄호를 스택에 push하고 닫는 괄호를 만나면 여는 괄호가 나올 때까지 스택의 연산자를 pop한다.
2 - 2. 아래 경우에는 곱하기 연산보다 더하기 연산이 먼저 실행되어야 하므로, 연산자를 만났을 때 여는 괄호 너머까지 pop 하지 않도록 여는 괄호의 우선순위는 가장 낮에 설정해야 한다.
3. 스택이 비어 모든 연산자가 쓰일 때 1, 2번을 반복한다.
[중위] A * (B + C)
[후위] ABC + *- 코드로 구현하기
# 연산자의 우선순위
prec = {
'*': 3, '/': 3,
'+': 2, '-': 2,
'(': 1
}
def solution(S):
opStack = ArrayStack()
answer = ''
for x in S:
# 피연산자일 경우
if x.isalpha():
answer += x
else:
# 여는 괄호일 경우
if x == '(':
opStack.push(x)
# 닫는 괄호일 경우
elif x == ')':
while not opStack.isEmpty():
curr = opStack.pop()
if curr == '(':
break
answer += curr
# 연산자일 경우
else:
if opStack.isEmpty():
opStack.push(x)
continue
while not opStack.isEmpty():
prev = opStack.peek()
# 스택에 있는 연산자의 우선순위가 높을 경우 pop
if prec[prev] >= prec[x]:
answer += opStack.pop()
else:
break
opStack.push(x)
# print(opStack.size())
while not opStack.isEmpty():
answer += opStack.pop()
return answer- 스택의 응용 2 - 후위 표기 수식 계산하기
1. 수식을 왼쪽부터 차례대로 읽어들인다.
2. 피연산자일 경우, 스택에 push한다.
3. 연산자일 경우, 스택에 들어있는 피연산자들 두 개 pop하여 연산을 적용하고, 그 결과를 다시 스택에 push한다. 빼기 혹은 나누기 연산일 경우에는 피연산자의 처리 순서가 중요하므로 이를 고려해야 한다.
4. 수식의 끝에 도달하면, 마지막엔 하나의 원소(연산 결과)가 스택에 남아있게 된다.
- 코드로 구현하기
# 후위 표기법 순서로 연산자 및 피연산자가 담긴 tokenList를 인자로 갖는 함수
def postfixEval(tokenList):
opStack = ArrayStack()
for token in tokenList:
if type(token) is int:
opStack.push(token)
else:
num2 = opStack.pop()
num1 = opStack.pop()
if token == '*':
opStack.push(num1 * num2)
elif token == '/':
opStack.push(num1 / num2)
elif token == '-':
opStack.push(num1 - num2)
elif token == '+':
opStack.push(num1 + num2)
return opStack.pop()큐(Queues)
자료를 넣을 때는 한쪽 끝에서 밀어 넣어야 하고 꺼낼 때에는 반대쪽에서 뽑아 꺼내야 하는 제약이 있는 선형 자료 구조. 선입선출(FIFO: first-in-first-out)
-
큐의 연산
-.enqueue(x): 원소 x를 큐에 넣는 동작
-.dequeue(): 큐의 맨 앞에 저장된 원소를 제거(또한, 반환) -
큐의 추상적 자료 구조 구현
- 배열 이용
dequeue() 연산의 시간 복잡도 O(N)가 배열의 길이에 비례 하게 된다.
- 이중 연결 리스트 이용
class LinkedListQueue:
def __init__(self):
self.data = DoublyLinkedList()
def size(self):
return self.data.getLength()
def isEmpty(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환형 큐(Circular Queue)
정해진 개수의 저장 공간을 빙 돌려가며 이용한다.
- 큐의 활용
- 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로 일어나는 경우- 자료를 생성하는 작업이 여러 곳에서 일어나는 경우
- 자료를 이용하는 작업이 여러 곳에서 일어나는 경우
- 자료를 생성하는 작업과 그 자료를 이용하는 작업이 양쪽 다 여러 곳에서 일어나는 경우
- 자료를 처리하여 새로운 자료를 생성하고, 나중에 그 자료를 또 처리해야 하는 작업의 경우
- 환형 큐의 특징
- front, rear로 자료 입력 시작점과 끝점을 처리한다.
- 큐가 가득 차면 더 이상 원소를 넣을 수 없으므로 큐 길이를 기억하고 있어야 한다.
-isFull()연산을 구현해 큐에 데이터 원소가 꽉 차 있는지를 판단하자.
- 배열로 구현하기
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)
큐가 FIFO 방식을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져나오는 방식을 갖는 자료구조.
- 우선순위 큐의 구현
- enqueue 할 때 우선순위 순서를 유지하도록 (더 효율적인 방법)- dequeue 할 때 우선순위 높은 것을 선택
- 선형 배열 이용
- 연결 리스트 이용 (원소를 중간에 삽입하기 용이하므로 시간적으로 유리)
- enqueue 연산 구현
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 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
트리(Trees)
node와 edge를 이용하여 데이터의 배치 형태를 추상화한 자료구조. 나무를 거꾸로 한 모습의 2차원 구조이다.
-
주요 용어
노드 (nodes)
간선 (edges)
루트 노드 (root node)
리프 노드 (leaf nodes): 차수가 0인 노드
내부 노드 (internal nodes)
부모 (parent) 노드와 자식 (child) 노드
노드의 수준 (level): root node는 level 0
노드의 차수 (degree): 특정 노드의 입장에서 자식(서브트리)의 수 = 자식으로 연결되는 간선의 개수
트리의 높이 (height) 또는, 깊이 (depth): 최대 수준(level) + 1
부분 트리 (서브트리; subtrees) -
포화 이진 트리 (full binary trees): 모든 레벨에서 노드들이 모두 채워져 있는 이진 트리
- 높이가 k일 때 노드의 개수는 2^k - 1 -
완전 이진 트리 (complete binary trees)
- 높이 k일 때 레벨 k - 2까지는 모든 노드가 2개 자식을 가진 포화 이진 트리
- 레벨 k - 1에서는 왼쪽부터 노드가 순차적으로 채워져 있는 이진 트리
이진 트리(Binary Tree)
트리에 포함되는 모든 노드의 차수가 2 이하인 트리
-
재귀적 정의
- 루트 노드 + 왼쪽 서브트리 + 오른쪽 서브트리 (단, 이 때 왼쪽과 오른쪽 서브트리 또한 이진 트리)
- 빈 트리도 이진트리로 정의한다. (재귀 호출의 종료조건) -
구현 - size(): 트리의 노드 개수
- 전체 이진 트리의 size = left subtree의 size + right subtree의 size + 1(자기 자신)
-
구현 - depth()
- 전체 이진 트리의 depth = left subtree의 depth와 right subtree의 depth 중 더 큰 것 + 1 -
깊이 우선 순회(deapth first traversal)
- 중위 순회(in-order traversal)
- 순회 순서: left subtree - 자기 자신 - right subtree
- 왼쪽 서브트리를 순회한 뒤 노드 x 를 방문, 그리고 나서 오른쪽 서브트리를 순회
- 전위 순회(pre-order traversal)
- 순회 순서: 자기 자신 - left subtree - right subtree
- 노드 x 를 방문한 후에 왼쪽 서브트리를 순회, 마지막으로 오른쪽 서브트리를 순회
- 후위 순회(post-order traversal)
- 순회 순서: left subtree - right subtree - 자기 자신
- 왼쪽 서브트리를 순회, 오른쪽 서브트리를 순회, 그리고 나서 마지막으로 노드 x 를 방문
- 중위 순회(in-order traversal)
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.preorder()
if self.right:
traversal += self.right.preorder()
return traversal
# 후위 순회
def postorder(self):
traversal = []
if self.left:
traversal += self.left.postorder()
if self.right:
traversal += self.right.postorder()
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)이 낮은 노드를 우선으로 방문
- 같은 수준의 노드들 사이에는, 부모 노드의 방문 순서에 따라 방문
- 왼쪽 자식 노드를 오른쪽 자식 노드보다 먼저 방문
- 큐를 이용한 구현
- 한 노드를 방문했을 때, 나중에 방문할 노드들(자식 노드)을 순서대로(왼쪽, 오른쪽) 기록(큐에 삽입)해 두어야 한다.
- 알고리즘 구현
- (초기화) traversal <- 빈 리스트, q <- 빈 큐
- 빈 트리가 아니면, root node를 큐에 추가(enqueue)
- q가 비어 있지 않은 동안, node <- q에서 꺼냄(dequeue), node를 방문, node의 왼쪽, 오른쪽 자식이 있으면 q에 순서대로 추가
- q가 빈 큐가 되면 모든 노드 방문 완료
class ArrayQueue:
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]
class Node:
def __init__(self, item):
self.data = item
self.left = None
self.right = None
class BinaryTree:
def __init__(self, r):
self.root = r
def bft(self):
traversal = []
q = ArrayQueue()
if self.root:
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
def solution(x):
return 0이진 탐색 트리(Binary Search Tree)
모든 노드에 대해서 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰 성질을 만족하는 이진 트리
- 정렬된 배열을 이용한 이진 탐색과 비교
- 장점: 데이터 원소의 추가, 삭제가 용이- 단점: 공간 소요가 큼, 한쪽으로 치우친 트리의 경우 탐색 연산의 복잡도가 선형 탐색과 비슷해짐
- 이진 탐색 트리의 추상적 자료구조
- 데이터 표현: 각 노드는 (key, value)의 쌍으로- 연산의 정의
- insert(key, data): 트리에 주어진 데이터 원소를 추가
- remove(key): 특정 원소를 트리로부터 삭제
- lookup(key): 특정 원소를 검색, 찾은 노드와 그것의 부모 노드 반환(remove 연산에 사용하기 위함)
- inorder(): 키의 순서대로 데이터 원소를 나열(중위 순회)
- min(), max(): 최소, 최대 키를 가지는 원소를 각각 탐색
- insert(key, data): 트리에 주어진 데이터 원소를 추가
- 연산의 정의
class Node:
def __init__(self, key, data):
self.key = key
self.data = data
self.left = None
self.right = None
def insert(self, key, data):
# 왼쪽에 들어가야 하는 경우
if key < self.key:
if self.left:
return self.left.insert(key, data)
else:
self.left = Node(key, data)
# 오른쪽에 들어가야 하는 경우
elif key > self.key:
if self.right:
return self.right.insert(key, data)
else:
self.right = Node(key, data)
else:
raise KeyError('중복된 노드 존재')
def lookup(self, key, parent=None):
# 지금 방문된 노드(self.key)보다 키가 작으면 왼쪽으로
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
def max(self):
if self.right:
return self.right.max()
else:
return self
class BinSearchTree:
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 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):
if self.root:
return self.root.min()
else:
return None
def max(self):
if self.root:
return self.root.max()
else:
return None
def solution(x):
return 0- 이진 탐색 트리에서 원소 삭제하기
1. 키를 이용해서 노드를 찾는다.- 해당 키의 노드가 없으면, 삭제할 것도 없음
- 찾은 노드의 부모 노드도 알고 있어야 함
- 찾은 노드를 제거하고도 이진 탐색 트리 성질을 만족하도록 트리의 구조를 정리한다. 삭제되는 노드가 무엇이냐에 따라 다르게 처리해야 한다.
- 말단 노드인 경우: 그 노드를 없애고 부모 노드의 링크를 조정
- 자식을 하나 가지고 있는 경우: 삭제되는 노드 자리에 그 자식을 대신 배치, 부모 노드의 링크 조정
- 자식을 둘 가지고 있는 경우: 삭제되는 노드보다 바로 다음 (큰 or 작은) 키를 가지는 노드를 찾아 그 노드를 삭제되는 노드 자리에 대신 배치하고 이 노드를 대신 삭제
class BinSearchTree:
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 lookup(self, key):
if self.root:
return self.root.lookup(key)
else:
return None, None
def remove(self, key):
node, parent = self.lookup(key)
if node:
nChildren = node.countChildren()
# 자식이 없는 노드를 삭제하려고 할 때
if nChildren == 0:
# 만약 parent 가 있으면
# node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
# parent.left 또는 parent.right 를 None 으로 하여
# leaf node 였던 자식을 트리에서 끊어내어 없앱니다.
if parent:
if parent.left == node:
parent.left = None
if parent.right == node:
parent.right = None
# 만약 parent 가 없으면 (node 는 root 인 경우)
# self.root 를 None 으로 하여 빈 트리로 만듭니다.
else:
self.root = None
# 자식이 하나 있는 노드를 삭제하려고 할 때
elif nChildren == 1:
# 하나 있는 자식이 왼쪽인지 오른쪽인지를 판단하여
# 그 자식을 어떤 변수가 가리키도록 합니다.
if node.left:
newnode = node.left
else:
newnode = node.right
# 만약 parent 가 있으면
# node 가 왼쪽 자식인지 오른쪽 자식인지 판단하여
# 위에서 가리킨 자식을 대신 node 의 자리에 넣습니다.
if parent:
if parent.left == node:
parent.left = newnode
else:
parent.right = newnode
# 만약 parent 가 없으면 (node 는 root 인 경우)
# self.root 에 위에서 가리킨 자식을 대신 넣습니다.
else:
self.root = newnode
# 자식이 둘 있는 노드를 삭제하려고 할 때
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
def inorder(self):
if self.root:
return self.root.inorder()
else:
return []
힙(Heaps)
루트 노드가 언제나 최댓값 또는 최솟값을 가지며 완전 이진 트리이다. 힙 내의 임의의 노드를 루트로 하는 서브트리 또한 힙이다.
- 이진 탐색 트리와의 비교
| 이진 탐색 트리 | 힙 | |
|---|---|---|
| 원소들이 완전히 크기 순으로 정렬되어 있는가? | O | X |
| 특정 키 값을 가지는 원소를 빠르게 검색할 수 있는가? | O | X |
| 부가의 제약 조건은 어떤 것인가? | 완전 이진 트리 |
-
최대 힙의 장점
- 완전 이진 트리여야 한다는 제약 때문에, n개 노드로 이루어진 최대 힙의 높이는 logN + 1
- 데이터 원소의 삽입/삭제 연산의 실행 시간은 언제나 logN에 비례
- 최대 힙으로부터 반복적으로 루트 노드를 꺼내면 logN 시간에 비례하여 데이터를 내림차순으로 정렬할 수 있음- 힙 정렬 알고리즘의 복잡도는 O(NlogN)로 정렬 알고리즘 복잡도 중 최소임
-
최대 힙의 추상적 자료구조
- 연산의 정의- insert(item): 새로운 원소를 삽입
- remove(): 최대 원소(root node)를 반환, 동시에 이 노드를 삭제
-
배열을 이용한 이진 트리의 표현
- 최대 힙에 원소 삽입
1. 트리의 마지막 자리에 새로운 원소를 임시로 저장- 부모 노드와 키 값을 비교하여 위로, 위로 이동
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 // 2] < self.data[m]:
self.data[m // 2], self.data[m] = self.data[m], self.data[m // 2]
m = m // 2
else:
break- 최대 힙에서 원소 삭제
1. 루트 노드(원소들 중 최댓값)의 제거- 트리 마지막 자리 노드를 임시로 루트 노드의 자리에 배치
- 자식 노드들과의 값을 비교하여 아래로, 아래로 이동(자식이 둘 있는 경우 둘 중 더 큰 값을 기준으로 내려감)
class MaxHeap:
def __init__(self):
self.data = [None]
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 child) 의 인덱스를 계산합니다.
left = 2 * i
# 오른쪽 자식 (right child) 의 인덱스를 계산합니다.
right = 2 * i + 1
smallest = i
# 왼쪽 자식이 존재하는지, 그리고 왼쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
if left < len(self.data) and self.data[left] > self.data[smallest]:
# 조건이 만족하는 경우, smallest 는 왼쪽 자식의 인덱스를 가집니다.
smallest = left
# 오른쪽 자식이 존재하는지, 그리고 오른쪽 자식의 (키) 값이 (무엇보다?) 더 큰지를 판단합니다.
if right < len(self.data) and self.data[right] > self.data[smallest]:
# 조건이 만족하는 경우, smallest 는 오른쪽 자식의 인덱스를 가집니다.
smallest = right
if smallest != i:
# 현재 노드 (인덱스 i) 와 최댓값 노드 (왼쪽 아니면 오른쪽 자식) 를 교체합니다.
self.data[i], self.data[smallest] = self.data[smallest], self.data[i]
# 재귀적 호출을 이용하여 최대 힙의 성질을 만족할 때까지 트리를 정리합니다.
self.maxHeapify(smallest)
하루하루 성장중