파이썬 자료구조와 알고리즘(7)-추상 데이터 타입
업데이트:
추상 데이터 타입(ADT)은 유사한 동작을 가진 자료구조의 클래스에 대한 수학적 모델이다.
크게 배열 기반의 연속 방식과 포인터 기반의 연결 방식으로 분류한다. 파이썬에서 연속 자료구조는 문자열, 리스트, 튜플 딕셔너리 등 이고 이번 장에서는 더 특화된 연속 구조의 예와 연결 구조(포인터에 연결된 메모리 청크)를 살펴본다.
1. 스택
후입선출(LIFO)구조. 스택의 연산은 다음과 같으며 모두 O(1)이다.
- push : 스택 맨 끝에 항목을 삽입한다.
- pop : 스택 끝 항목을 반환하고 제거한다.
- top/peek : 스택 맨 끝 항목을 조회한다.
- empty : 스택이 비어 있는지 확인한다
- size : 스택 크기를 확인한다.
스택은 깊이우선탐색(DFS)에서 유용하게 사용된다.
1.1 리스트로 스택 구현
class Stack(object):
def __init__(self):
self.items = []
def isEmpty(self):
return not bool(self.items)
def push(self, value):
self.items.append(value)
def pop(self):
value = self.items.pop()
if value is not None:
return value
else:
print('Stack is empty')
def size(self):
return len(self.items)
def peek(self):
if self.items:
return self.items[-1]
else:
print('Stack is Empty')
def __repr__(self):
return repr(self.items)
1.2 노드(객체)의 컨테이너로 스택 구현
class Node(object):
def __init__(self, value=None, pointer=None):
self.value = value
self.pointer = pointer
class Stack(object):
def __init__(self):
self.head = None
self.count = 0
def isEmpty(self):
return not bool(self.head)
def push(self, item):
self.head = Node(item, self.head) # 새 노드는 현 스택의 head를 가리킨다.
self.count += 1
def pop(self):
if self.count > 0 and self.head:
node = self.head
self.head = node.pointer
self.count -= 1
return node.value
else:
print('Stack is Empty')
def peek(self):
if self.count > 0 and self.head:
return self.head.value
else:
print('Stack is Empty')
def size(self):
return self.count
def _printList(self):
node = self.head
while node:
print(node.value, end=' ')
node = node.pointer
print()
2. 큐
선입선출(FIFO)구조. 큐의 연산은 다음과 같으며 모두 O(1)이다.
- enqueue : 큐 뒤쪽에 항목 삽입
- dequeue : 큐 앞쪽 항목 반환 후 제거
- peek/front : 큐 앞쪽 항목 조회
- empty : 큐가 비어 있는지 확인
- size : 큐의 크기를 확인
너비 우선 탐색(BFS)에서 사용된다.
2.1 큐 구현
insert()메소드를 이용하면 O(N)으로 비효율적이다.
class Queue(object):
def __init__(self):
self.items = []
def isEmpty(self):
return not bool(self.items)
def enqueue(self, item):
self.items.insert(0, item)
def dequeue(self):
value = self.items.pop()
if value is not None:
return value
else:
print('Queue is Empty')
def size(self):
return len(self.items)
def peek(self):
if self.items:
return self.items[-1]
else:
print('Queue is Empty')
def __repr__(self):
return repr(self.items)
2.2 두 개의 스택을 이용한 구현
insert() 메서드 쓰는 것보다 효율적이다.
class StackQueue(object):
def __init__(self):
self.in_stack = []
self.out_stack = []
def _transfer(self):
while self.in_stack:
self.out_stack.append(self.in_stack.pop())
def enqueue(self, item):
self.in_stack.append(item)
def dequeue(self):
if not self.out_stack:
self._transfer()
if self.out_stack:
return self.out_stack.pop()
else:
print('Queue is Empty')
def size(self):
return len(self.in_stack) + len(self.out_stack)
def peek(self):
if not self.out_stack:
self._transfer()
if self.out_stack:
return self.out_stack[-1]
else:
print('Queue is Empty')
def __repr__(self):
if not self.out_stack:
self._transfer()
if self.out_stack:
return repr(self.out_stack)
else:
print('Queue is Empty')
def isEmpty(self):
return not(bool(self.in_stack) or bool(self.out_stack))
2.3 노드(객체)의 컨테이너로 구현
class Node(object):
def __init__(self, value=None, pointer=None):
self.value = value
self.pointer = None
class LinkedQueue(object):
def __init__(self):
self.head = None
self.tail = None
self.count = 0
def isEmpty(self):
return not(bool(self.head))
def dequeue(self):
if self.head:
value = self.head.value
self.head = self.head.pointer
self.count -= 1
return value
else:
print('Queue is Empty')
def enqueue(self, item):
node = Node(item)
if not self.head:
self.head = node
self.tail = node
else:
if self.tail:
self.tail.pointer = node
self.tail = node
self.count += 1
def size(self):
return self.count
def peek(self):
return self.head.value
def _print(self):
node = self.head
while node:
print(node.value, end=' ')
node = node.pointer
print()
3. Deque
스택과 큐의 결합체이다. 양쪽 끝에서 조회, 삽입, 삭제가 가능하다
3.1 데크의 구현
큐를 바탕으로 구현할 수 있다.
# from queue import Queue
class Deque(Queue): # 상속
def enqueue_back(self, item):
self.items.append(item)
def dequeue_front(self):
value = self.items.pop(0)
if value is not None :
return value
else:
print('Deque is Empty')
3.2 deque 모듈을 이용한 구현
insert() 메서드를 사용하지 않아 효율적이다. q = deque(maxlen=4)와 같이 데크의 크기를 지정할 수 있다. 또한 rotate(n)메서드는 n이 양수이면 오른쪽으로, 음수이면 왼쪽으로 n만큼 시프트한다.
deque 모듈은 배열이 아닌 이중 연결 리스트를 기반으로 구현되었다.
from collections import deque
q = deque(['버피', '젠더', '윌로'], maxlen=4)
print(q.popleft())
q.rotate(-1)
print(q)
q.rotate(1)
print(q)
버피
deque(['윌로', '젠더'], maxlen=4)
deque(['젠더', '윌로'], maxlen=4)
4. 우선순위 큐와 힙
스택, 큐와 비슷하지만 각 항목마다 우선순위가 있다. 우선순위가 같으면 큐의 순서를 따른다. 힙을 사용하여 구현한다.
4.1 힙
각 노드가 하위 노드보다 작은 이진 트리다.균형 트리의 모양이 수정될 때, 다시 균형 트리로 만드는 시간복잡도는 O(logN)이다.
리스트에서 가장 작은(또는 가장 큰) 요소에 반복적으로 접근하는 프로그램에 유용하다. 가장 작은(큰) 요소를 처리하는 시간복잡도는 O(1)이고, 조회, 추가, 수정 연산은 O(logN)이다.
4.2 heapq 모듈
heapq.heapify()함수를 사용하여 O(N)시간에 리스트를 힙으로 변환할 수 있다.
import heapq
list1 = [4,6,8,1]
heapq.heapify(list1)
list1
[1, 4, 8, 6]
h = []
heapq.heappush(h, (1,'food'))
heapq.heappush(h, (2,'fun'))
heapq.heappush(h, (3,'work'))
heapq.heappush(h, (4,'study'))
h
[(1, 'food'), (2, 'fun'), (3, 'work'), (4, 'study')]
print(heapq.heappop(list1))
print(list1)
1
[4, 6, 8]
for x in heapq.merge([1,3,5],[2,4,6]):
print(x)
1
2
3
4
5
6
heapq.nlargest(3, [1,2,3,4,5,6])
[6, 5, 4]
4.3 최대 힙 구현하기
책 참조할것
class Heapify(object):
def __init__(self, data=None):
self.data = data or []
for i in range(len(data)//2, -1, -1):
self.__max_heapify__(i)
def __repr__(self):
return repr(self.data)
def parent(self, i):
if i & 1:
return i >> 1
else:
return (i >> 1) - 1
def left_child(self, i):
return (i << 1) + 1
def right_child(self, i):
return (i << 1) + 2
def __max_heapify__(self, i):
largest = i # 현재 노드
left = self.left_child(i)
right = self.right_child(i)
n = len(self.data)
# 왼쪽 자식
largest = (left < n and self.data[left] > self.data[i]) and left or i
# 오른쪽 자식
largest = (right < n and self.data[right] > self.data[largest]) and \
right or largest
# 현재 노드가 자식들보다 크다면 Skip, 자식이 크다면 Swap
if i is not largest:
self.data[i], self.data[largest] = self.data[largest], self.data[i]
# print(self.data)
self.__max_heapify__(largest)
def extract_max(self):
n = len(self.data)
max_element = self.data[0]
# 첫 번째 노드에 마지막 노드를 삽입
self.data[0] = self.data[n - 1]
self.data = self.data[:n - 1]
self.__max_heapify__(0)
return max_element
def insert(self, item):
i = len(self.data)
self.data.append(item)
while (i != 0) and item > self.data[self.parent(i)]:
print(self.data)
self.data[i] = self.data[self.parent(i)]
i = self.parent(i)
self.data[i] = item
def test_heapify():
l1 = [3, 2, 5, 1, 7, 8, 2]
h = Heapify(l1)
assert(h.extract_max() == 8)
print("테스트 통과!")
if __name__ == "__main__":
test_heapify()
테스트 통과!
4.4 우선순위 큐 구현하기
import heapq
class PriorityQueue(object):
def __init__(self):
self._queue = []
self._index = 0
def push(self, item, priority):
heapq.heappush(self._queue, (-priority, self._index, item))
self._index += 1
def pop(self):
return heapq.heappop(self._queue)[-1]
class Item:
def __init__(self, name):
self.name = name
def __repr__(self):
return 'Item({0!r})'.format(self.name)
5. 연결 리스트
런타임에 저장할 항목의 수를 알 수 없을 때 유용하다. 삽입 O(1), 검색 및 삭제 O(N), 연결 리스트의 뒤부터 순회하거나 정렬하는 경우 O(N^2), 노드의 포인터를 알고 있을 때 삭제 O(1)이다.
class Node(object):
def __init__(self, value=None, pointer=None):
self.value = value
self.pointer = pointer
def getData(self):
return self.value
def getNext(self):
return self.pointer
def setData(self, newdata):
self.value = newdata
def setNext(self, newpointer):
self.pointer = newpointer
class LinkedListLIFO(object):
def __init__(self):
self.head = None
self.length = 0
# 헤드부터 각 노드의 값 출력
def _printList(self):
node = self.head
while node:
print(node.value, sep=' ')
node = node.pointer
print()
# 이전 노드를 기반으로 노드를 삭제한다
def _delete(self, prev, node):
self.length -= 1
if not prev:
self.head = node.pointer
else:
prev.pointer = node.pointer
# 새 노드를 추가한다
def _add(self, value):
self.length += 1
self.head = Node(value, self.head)
# 인덱스로 노드를 찾는다
def _find(self, index):
prev = None
node = self.head
i = 0
while node and i < index:
prev = node
node = node.pointer
i += 1
return node, prev, i
# 값으로 노드를 찾는다.
def _find_by_value(self, value):
prev = None
node = self.head
found = False
while node and not found:
if node.value == value:
found = True
else:
prev = node
node = node.pointer
return node, prev, found
# 인덱스 노드를 찾아 삭제
def deleteNode(self, index):
node, prev, i = self._find(index)
if index == i:
self._delete(prev, node)
else:
print(f'인덱스{index}에 해당하는 노드가 없습니다')
# 값에 해당하는 노드 찾아 삭제
def deleteNodeByValue(self, value):
node, prev, found = self._find_by_value(value)
if found:
self._delete(prev, node)
else:
print(f'값{value}에 해당하는 노드가 없습니다')
class LinkedListFIFO(object):
def __init__(self):
self.head = None # 헤드(머리)
self.length = 0
self.tail = None # 테일(꼬리)
# 헤드부터 각 노드의 값을 출력한다.
def _printList(self):
node = self.head
while node:
print(node.value, end=" ")
node = node.pointer
print()
# 첫 번째 위치에 노드를 추가한다.
def _addFirst(self, value):
self.length = 1
node = Node(value)
self.head = node
self.tail = node
# 첫 번째 위치의 노드를 삭제한다.
def _deleteFirst(self):
self.length = 0
self.head = None
self.tail = None
print("연결 리스트가 비었습니다.")
# 새 노드를 추가한다. 테일이 있다면, 테일의 다음 노드는
# 새 노드를 가리키고, 테일은 새 노드를 가리킨다.
def _add(self, value):
self.length += 1
node = Node(value)
if self.tail:
self.tail.pointer = node
self.tail = node
# 새 노드를 추가한다.
def addNode(self, value):
if not self.head:
self._addFirst(value)
else:
self._add(value)
# 인덱스로 노드를 찾는다.
def _find(self, index):
prev = None
node = self.head
i = 0
while node and i < index:
prev = node
node = node.pointer
i += 1
return node, prev, i
# 값으로 노드를 찾는다.
def _find_by_value(self, value):
prev = None
node = self.head
found = False
while node and not found:
if node.value == value:
found = True
else:
prev = node
node = node.pointer
return node, prev, found
# 인덱스에 해당하는 노드를 삭제한다.
def deleteNode(self, index):
if not self.head or not self.head.pointer:
self._deleteFirst()
else:
node, prev, i = self._find(index)
if i == index and node:
self.length -= 1
if i == 0 or not prev:
self.head = node.pointer
self.tail = node.pointer
else:
prev.pointer = node.pointer
else:
print("인덱스 {0}에 해당하는 노드가 없습니다.".format(index))
# 값에 해당하는 노드를 삭제한다.
def deleteNodeByValue(self, value):
if not self.head or not self.head.pointer:
self._deleteFirst()
else:
node, prev, i = self._find_by_value(value)
if node and node.value == value:
self.length -= 1
if i == 0 or not prev:
self.head = node.pointer
self.tail = node.pointer
else:
prev.pointer = node.pointer
else:
print("값 {0}에 해당하는 노드가 없습니다.".format(value))
6. 해시 테이블
key를 value에 연결하여 하나의 키가 0 또는 1개의 값과 연관된다. 각 키는 hash function을 계산할 수 있어야 한다. 해시 테이블은 hash bucket의 배열로 구성된다. 해시 값이 42이고 5개의 버킷이 있는 경우 42%5 = 2에 매핑한다
두 개의 키가 동일한 버킷에 해시될 때 해시 충돌 이를 처리하기 위해 각 버킷에 대해 key-value pair linked list를 저장한다.
조회, 삽입, 삭제 O(1)이다. 최악의 경우 각 키가 해시 충돌시 O(N)이다.
class HashTableLL(object):
def __init__(self, size):
self.size = size
self.slots = []
self._createHashTable()
def _createHashTable(self):
for i in range(self.size):
self.slots.append(LinkedListFIFO())
def _find(self, item):
return item % self.size
def _add(self, item):
index = self._find(item)
self.slots[index].addNode(item)
def _delete(self, item):
index = self._find(item)
self.slots[index].deleteNodeByValue(item)
def _print(self):
for i in range(self.size):
print(f'슬롯 {i}:')
self.slots[i]._printList()
7. 연습문제
7.1 스택
데이터를 역순으로 정렬하거나 검색할 때 사용한다.
문자열 뒤집기
def reverse_string_with_stack(str1):
stack = Stack()
revStr = ''
for ch in str1:
stack.push(ch)
while not stack.isEmpty():
revStr += stack.pop()
return revStr
str1 = '버피는 천사다'
reverse_string_with_stack(str1)
'다사천 는피버'
괄호의 짝 확인하기
def balance_par_str_with_stack(str1):
s = Stack()
balanced = True
index = 0
while index < len(str1) and balanced:
symbol = str1[index]
if symbol == '(':
s.push(symbol)
else:
if s.isEmpty():
balanced = False
else:
s.pop()
index += 1
if not s.isEmpty():
balanced = False
return balanced
print(balance_par_str_with_stack('((()))'))
print(balance_par_str_with_stack('(((()))'))
True
False
# 10진수를 2진수로 변환하기
def dec2bin_with_stack(decNum):
s = Stack()
while decNum > 0:
s.push(decNum % 2)
decNum = decNum // 2
res = ''
while not s.isEmpty():
res += str(s.pop())
return res
dec2bin_with_stack(9) # 1001
'1001'
스택에서 최솟값 조회하기
class NodeWithMin(object):
def __init__(self, value=None, minimum=None):
self.value = value
self.minimum = minimum
class StackMin(Stack):
def __init__(self):
self.items = []
self.minimum = None
def push(self, value):
if self.isEmpty() or self.minimum > value:
self.minimum = value
self.items.append(NodeWithMin(value, self.minimum))
def peek(self):
return self.items[-1].value
def peekMinimum(self):
return self.items[-1].minimum
def pop(self):
item = self.items.pop()
if item:
if item.value == self.minimum:
self.minimum = self.peekMinimum
else:
print('Stack is Empty')
def __repr__(self):
aux = []
for i in self.items:
aux.append(i.value)
return repr(aux)
스택 집합
스택에 ‘용량’이 있을 때 초과 시에 새 스택을 만들어야 한다. 이 경우 여러 스택의 집합에서도 단일 스택과 같이 pop()과 push()를 하려면?
class SetOfStacks(Stack):
def __init__(self, capacity=4):
self.setofstacks = []
self.items = []
self.capacity = 4
def push(self, value):
if self.size() >= self.capacity:
self.setofstacks.append(self.items)
self.items = []
self.items.append(value)
def pop(self):
value = self.items.pop()
if self.isEmpty() and self.setofstacks:
self.items = self.setofstacks.pop()
return value
def sizeStack(self):
return len(self.setofstacks) * self.capacity + self.size()
def __repr__(self):
aux = []
for s in self.setofstacks:
aux.extend(s)
aux.extend(self.items)
return repr(aux)
7.2 큐
데크와 회문
from collections import deque
import string
def palindrome_checker_with_deque(str1):
STRIP = string.whitespace + string.punctuation + "\"'"
dq = deque()
for i in str1.lower():
if i not in STRIP:
dq.append(i)
while len(dq) > 1:
if dq.popleft() != dq.pop():
return False
else:
return True
str1 = 'Madam Im Adam'
str2 = 'Buffy is a Slayer'
print(palindrome_checker_with_deque(str1))
print(palindrome_checker_with_deque(str2))
True
False
큐와 동물 보호소
class Node(object):
def __init__(self, animalName=None, animalKind=None, pointer=None):
self.animalName = animalName
self.animalKind = animalKind
self.pointer = pointer
self.timestamp = 0
class AnimalShelter(object):
def __init__(self):
self.headCat = None
self.headDog = None
self.tailCat = None
self.tailDog = None
self.animalNumber = 0
def enqueue(self, animalName, animalKind):
self.animalNumber += 1
newAnimal = Node(animalName, animalKind)
newAnimal.timestamp = self.animalNumber
if animalKind == "cat":
if not self.headCat:
self.headCat = newAnimal
if self.tailCat:
self.tailCat.pointer = newAnimal
self.tailCat = newAnimal
elif animalKind == "dog":
if not self.headDog:
self.headDog = newAnimal
if self.tailDog:
self.tailDog.pointer = newAnimal
self.tailDog = newAnimal
def dequeueDog(self):
if self.headDog:
newAnimal = self.headDog
self.headDog = newAnimal.pointer
return str(newAnimal.animalName)
else:
print("개가 없습니다!")
def dequeueCat(self):
if self.headCat:
newAnimal = self.headCat
self.headCat = newAnimal.pointer
return str(newAnimal.animalName)
else:
print("고양이가 없습니다!")
def dequeueAny(self):
if self.headCat and not self.headDog:
return self.dequeueCat()
elif self.headDog and not self.headCat:
return self.dequeueDog()
elif self.headDog and self.headCat:
if self.headDog.timestamp < self.headCat.timestamp:
return self.dequeueDog()
else:
return self.dequeueCat()
else:
print("동물이 없습니다.")
def _print(self):
print("고양이:")
cats = self.headCat
while cats:
print("\t{0}".format(cats.animalName))
cats = cats.pointer
print("개:")
dogs = self.headDog
while dogs:
print("\t{0}".format(dogs.animalName))
dogs = dogs.pointer
if __name__ == "__main__":
qs = AnimalShelter()
qs.enqueue("밥", "cat")
qs.enqueue("미아", "cat")
qs.enqueue("요다", "dog")
qs.enqueue("울프", "dog")
qs._print()
print("하나의 개와 고양이에 대해서 dequeue를 실행합니다.")
qs.dequeueDog()
qs.dequeueCat()
qs._print()
고양이:
밥
미아
개:
요다
울프
하나의 개와 고양이에 대해서 dequeue를 실행합니다.
고양이:
미아
개:
울프
7.3 우선순위 큐와 힙
시퀀스에서 N개의 가장 큰 항목과 가장 작은 항목을 찾아보자
import heapq
def find_N_largest_items_seq(seq, N):
return heapq.nlargest(N, seq)
def find_N_largest_items_seq(seq, N):
return heapq.nsmallest(N, seq)
정렬된 두 시퀀스를 적은 비용으로 병합해보자. O(logN)
import heapq
def merge_sorted_seqs(seq1, seq2):
result = []
for c in heapq.merge(seq1, seq2):
result.append(c)
return result
7.4 연결 리스트
끝에서 k번째 항목 찾기
# p1 : 연결 리스트 전부 순회
# p2 : k-1 이후를 순회
class KthFromLast(LinkedListFIFO):
def find_kth_to_last(self, k):
p1, p2 = self.head, self.head
i = 0
while p1:
if i > k-1:
try:
p2 = p2.pointer
except AttributeError:
break
p1 = p1.pointer
i += 1
return p2.value
연결 리스트 분할하기
항목의 왼쪽에는 작은 숫자, 오른쪽에는 큰 숫자가 나오도록 분할해보자
def partList(ll, n):
more = LinkedListFIFO()
less = LinkedListFIFO()
node = ll.head
while node:
item = node.value
if item < n:
less.addNode(item)
else:
more.addNode(item)
node = node.pointer
less.addNode(n)
nodemore = more.head
while nodemore:
less.addNode(nodemore.value)
nodemore = nodemore.pointer
return less
ll = LinkedListFIFO()
l = [6, 7, 3, 4, 9, 5, 1, 2, 8]
for i in l:
ll.addNode(i)
newll = partList(ll, 6)
newll._printList()
3 4 5 1 2 6 6 7 9 8
이중 연결 리스트와 FIFO
class DNode(object):
def __init__(self, value=None, pointer=None, previous=None):
self.value = value
self.pointer = pointer
self.previous = previous
class DLinkedList(LinkedListFIFO):
def printListInverse(self):
node = self.tail
while node:
print(node.value, end=" ")
try:
node = node.previous
except AttributeError:
break
print()
def _add(self, value):
self.length += 1
node = DNode(value)
if self.tail:
self.tail.pointer = node
node.previous = self.tail
self.tail = node
def _delete(self, node):
self.length -= 1
node.previous.pointer = node.pointer
if not node.pointer:
self.tail = node.previous
def _find(self, index):
node = self.head
i = 0
while node and i < index:
node = node.pointer
i += 1
return node, i
def deleteNode(self, index):
if not self.head or not self.head.pointer:
self._deleteFirst()
else:
node, i = self._find(index)
if i == index:
self._delete(node)
else:
print("인덱스 {0}에 해당하는 노드가 없습니다.".format(index))
if __name__ == "__main__":
from collections import Counter
ll = DLinkedList()
for i in range(1, 5):
ll.addNode(i)
print("연결 리스트 출력:")
ll._printList()
print("연결 리스트 반대로 출력:")
ll.printListInverse()
print("값이 15인 노드 추가 후, 연결 리스트 출력:")
ll._add(15)
ll._printList()
print("모든 노드 모두 삭제 후, 연결 리스트 출력:")
for i in range(ll.length-1, -1, -1):
ll.deleteNode(i)
ll._printList()
연결 리스트 출력:
1 2 3 4
연결 리스트 반대로 출력:
4 3 2 1
값이 15인 노드 추가 후, 연결 리스트 출력:
1 2 3 4 15
모든 노드 모두 삭제 후, 연결 리스트 출력:
연결 리스트가 비었습니다.
회문 확인하기
일단 여기까지
댓글남기기