7-1. 추상 데이터 타입 (Abstract Data Type): 파이썬 자료구조와 알고리즘

 

추상 데이터 타입 (abstract data type, ADT) 은 유사한 동작을 가진 자료구조의 클래스에 대한 수학적 모델을 가리킨다. 자료구조는 크게 배열 기반의 연속 (continuation) 방식과 포인터 기반의 연결 (link) 방식으로 분류한다. 예를들어. 연속적 할당 자료구조는 문자열, 리스트, 튜플, 딕셔너리 등이 있다. 그러나 앞으로 배울 내용들은 좀 더 특화된 연속 구조의 예와 연결 구조의 예를 살펴본다.

스택

스택 (stack) 은 배열의 끝에서만 데이터를 접근할 수 있는 선형 자료구조이다. 스택은 배열 인덱스 접근이 제한되며, 후입선출 (last in first out, LIFO) 구조이다. 책상 위에 쌓여 있는 책을 상상해보자. 맨 위의 책을 가져올 순 있지만, 맨 아래 또는 중간의 책은 꺼낼 수 없는 구조라고 생각하면 편하다.

스택의 동작은 다음과 같으며, 시간 복잡도는 모두 O(1) 이다.

• push: 스택의 맨 끝 (또는 맨 위) 에 항목을 삽입한다 (create).
• pop: 스택의 맨 끝 (또는 맨 위) 의 항목을 반환하는 동시에 제거한다 (delete).
• top/peek: 스택의 맨 끝 항목을 조회한다 (read).
• empty: 스택이 비어 있는지 확인한다.
• size: 스택 크기를 확인한다.

파이썬에서 다음과 같이 리스트의 append() 와 pop() 메서드로 스택을 구현할 수 있다.

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)

 

가장 기본적인 형태의 스택이다. 다음 코드는 노드 (객체) 의 컨테이너로 스택을 구현한다.

 

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)
        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()

 

하위 노드가 상위 노드를 포인터로 가리키고 있고 가장 위의 노드를 스택의 head로 지정해 보여주는 방식이다.

 

스택은 깊이 우선 탐색 (deep-first search) 에서 유용하게 사용된다. 이는 추후에 다뤄보자.

 

큐

큐 (queue) 는 스택과 반대이다. 들어온 순서대로 접근 가능하다. 이름 그대로 줄 서서 기다리는 사람들 (큐) 로 생각하면 쉽다. 즉, 먼저 들어온 데이터가 먼저 나가는 선입선출 (first in first out, FIFO) 구조이다. 큐의 동작은 다음과 같으며, 시간 복잡도는 모두 O(1) 이다.

• enqueue: 큐 뒤쪽에 항목을 삽입한다.
• dequeue: 큐 앞쪽의 항목을 반환 및 제거한다.
• peek/front: 큐 앞쪽의 항목을 조회한다.
• empty: 큐가 비어 있는지 확인한다.
• size: 큐의 크기를 확인한다.

큐를 리스트로 간단하게 구현하면 다음과 같다.

 

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)

 

먼저 나올 아이템이 리스트의 가장 마지막 항목에 위치하는 큐의 형태이다. 그러나 이 경우, 큐에 항목을 삽입할 때 insert() 메서드를 쓰고, 이는 메모리에서 모든 요소를 이동시키기 때문에 시간 복잡도 O(n) 을 갖고 있어 비효율적일 수 있다. 따라서 두 개의 스택을 사용하면 효율적인 큐를 다음과 같이 작성할 수 있다.

 

class Queue(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 isEmpty(self):
        return not (bool(self.in_stack) or bool(self.out_stack))

    def enqueue(self, item):
        return 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.")

 

in_stack 과 out_stack 을 각각 데이터가 들어오는 곳과 나가는 곳으로 분류하여 필요할 때마다 in_stack에서 out_stack으로 데이터를 옮기며 out_stack을 큐의 리스트로써 관리하는 방식이다.

 

다음 코드에서는 노드 (객체) 의 컨테이너로 큐를 구현한다.

 

class Node(object):
    def __init__(self, value=None, pointer=None):
        self.value = value
        self.pointer = pointer

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, value):
        node = Node(value)
        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()

가장 밑 (tail) 과 가장 위 (head) 가 존재하며, 데이터를 넣을 땐 가장 밑, 뺄 땐 가장 위의 데이터를 빼는 방식으로 동작하는 큐이다.

 

큐는 너비 우선 탐색 (BFS) 에서 사용된다.

 

데크

데크 (deque) 는 스택과 큐를 합친 것 같은 것이다. 양쪽 끝에서의 항목 조회, 삽입, 삭제가 가능하다. 이를 앞에서 구현한 큐를 바탕으로 구현해보자.

 

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")

 

이 경우 역시 끝이 아닌 다른 위치에 있는 항목을 삽입 또는 제거할 때 비효율적이다. 파이썬에서 제공하는 collections 패키지의 deque 모듈을 사용하면 이 문제를 해결할 수 있다.

 

>>> from collections import deque
>>> q = deque(['hello','world','beom','seok'])
>>> q
deque(['hello', 'world', 'beom', 'seok'])
>>> q.append('!!')
>>> q.popleft()
'hello'
>>> q.pop()
'!!'
>>> q
deque(['world', 'beom', 'seok'])
>>> q.appendleft('hello~')
>>> q
deque(['hello~', 'world', 'beom', 'seok'])

 

또한, deque 모듈을 사용하면 q = deque(maxlen=4) 와 같은 방식으로 데크의 크기를 지정할 수 있으며, rotate(n) 메서드는 n이 양수이면 오른쪽으로, n이 음수이면 왼쪽으로 n만큼 시프트 시킨다.

 

힙

힙 (heap) 은 각 노드가 하위 노드보다 작은 (또는 큰) 이진 트리이다. 힙은 최솟값 또는 최댓값을 빠르게 찾아내도록 만들어낸 구조이다. 최솟값이 맨 위에 위치하는 힙은 최소 힙 (min-heap) 이라고 하며, 최댓값이 맨 위에 위치하는 힙은 최대 힙 (max-heap) 이라고 한다. 힙은 느슨한 정렬 상태를 유지한다. 즉 완벽 정렬이라기보단 부모 노드가 자식 노드보다 규칙에 따라 크거나 작기만 하면 된다는 뜻이다.

 

균형 트리의 모양이 수정될 때, 이를 다시 균형 트리로 만드는 시간 복잡도는 O(log n) 이다. 힙은 일반적으로 리스트에서 가장 작은 (또는 가장 큰) 요소에 반복적으로 접근하는 프로그램에 유용하다. 최소 (또는 최대) 힙을 사용하면 가장 작은 (또는 가장 큰) 요소를 처리하는 시간 복잡도는 O(1) 이고, 그 외에 조회, 추가, 수정을 처리하는 시간 복잡도는 O(log n) 이다.

heapq 모듈

heapq 모듈은 효율적으로 시퀀스를 힙으로 유지하면서, 항목을 삽입하고 제거하는 함수를 제공한다. 다음과 같이, heapq.heapify() 함수를 사용하면 O(n) 시간에 리스트를 힙으로 변환할 수 있다.

 

>>> import heapq
>>> list1 = [4,6,8,1]
>>> heapq.heapify(list1)
>>> list1
[1, 4, 8, 6]

 

항목에 힙을 삽입할 땐 heapq.heappush(heap, item) 을 사용한다.

 

>>> h = []
>>> heapq.heappush(h, (1, 'food'))
>>> heapq.heappush(h, (2, 'have fun'))
>>> heapq.heappush(h, (3, 'work'))
>>> heapq.heappush(h, (4, 'study'))
>>> h
[(1, 'food'), (2, 'have fun'), (3, 'work'), (4, 'study')]

 

heapq.heappop(heap) 함수는 힙에서 가장 작은 항목을 제거하고 반환한다.

 

>>> h
[(1, 'food'), (2, 'have fun'), (3, 'work'), (4, 'study')]
>>> heapq.heappop(h)
(1, 'food')
>>> h
[(2, 'have fun'), (4, 'study'), (3, 'work')]

 

heapq.heappushpop(heap, item) 은 새 항목을 힙에 추가한 후, 가장 작은 항목을 제거하고 반환한다. heapq.heapreplace(heap, item) 는 힙의 가장 작은 항목을 제거하고 반환한 후 새 항목을 추가한다. 힙의 속성을 사옹하면 많은 연산을 할 수 있다. 예를 들어 heapq.merge(*iterables) 는 여러 개의 정렬된 반복 가능한 객체를 병합하여 하나의 정렬된 결과의 이터레이터를 반환한다.

 

>>> a = [1,2,5]
>>> b = [3,4,6]
>>> heapq.merge(a,b)
<generator object merge at 0x03AC2B88>
>>> for x in heapq.merge(a,b):
	print(x)

1
2
3
4
5
6

 

heapq.nlargest(n, iterable[, key]) 와 heapq.nsmallest(n, iterable[, key]) 는 데이터에서 n 개의 가장 큰 요소와 가장 작은 요소가 있는 리스트를 반환한다.

최대 힙 구현

최대 힙을 (max-heap) 을 예시로 리스트 [3, 2, 5, 1, 7, 8, 2] 를 힙으로 만들어 보겠다. 리스트를 트리로 표현해 보자.

동그라미는 각각 노드를 뜻하며 노드 안의 숫자는 값, 노드 밖의 숫자는 인덱스를 뜻한다. 규칙을 보면 노드 i 의 왼쪽 자식 노드의 인덱스는 2i+1 이고, 오른쪽 자식 노드의 인덱스는 2i+2 이다.

 

먼저 전체 배열의 길이를 반으로 나누자. 7//2 = 3 이다. 따라서 인덱스 3부터 보면서 인덱스 0까지 재배열해 보겠다.

 

  1. 인덱스 3을 보자. 인덱스 3 노드에는 자식 노드가 없다. 그러므로 넘어간다.

  2. 인덱스 2를 보자. 인덱스 2의 값은 5이다. 인덱스 2의 하위 노드 중 인덱스 5는 값이 8로, 인덱스 2 보다 크다. 따라서 이를 재배열해준다.

  3. 이제 인덱스 1을 보자. 인덱스 1의 값은 2이다. 인덱스 1의 하위 노드 중 인덱스 4는 값이 7로, 인덱스 1 보다 크다. 따라서 이를 재배열해준다.

  4. 이제 인덱스 0을 보자. 인덱스 0의 값은 3이다. 보면 두 자식 노드 (인덱스 1과 2) 모두 인덱스 0 보다 크지만 가장 큰 값을 가진 자식 노드는 인덱스 2이다. 따라서 인덱스 0과 인덱스 2의 값을 바꿔주자.

  4-1. 보면 바뀐 인덱스인 인덱스 2의 값이 그의 자식 노드인 인덱스 5의 값보다 작다. 이를 다시 재배열 해준다.

  5. 인덱스 0까지 비교를 마쳤으니 프로그램을 종료한다. 결과: [8, 7, 5, 1, 2, 3, 2]

이를 코드로 구현하면 다음과 같다.

 

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: # i가 홀수일 경우 (1과 비트가 겹치지 않는다.)
            return i >> 1 # i/2 (1비트만큼 오른쪽으로 옮기면 /2가 됨, 나머지 생략)
        else: # i가 짝수일 경우
            return (i >> 1) - 1 # i/2 -1

    def left_child(self, i): #자식 노드 인덱스 찾기
        return (i<<1) + 1 # 2i+1 (1비트만큼 왼쪽으로 옮기면 *2가 됨)
    def right_child(self, i):
        return (i<<1) + 2 # 2i+2
    
    def __max_heapify__(self, i):
        largest = i # 현재 노드 인덱스
        left = self.left_child(i) # 왼쪽 자식 노드 인덱스
        right = self.right_child(i) # 오른쪽 자식 노드 인덱스
        n = len(self.data)

        # 왼쪽 자식 노드 먼저 계산한다.
        # 먼저 왼쪽 노드가 존재하는지부터 확인.
        # 그 후 왼쪽 노드와 부모 노드 (현재 노드) 의 값을 비교한다.
        # 만약 true라면 (왼쪽 노드가 부모 노드보다 큰 값이라면), largest에 왼쪽 노드의 인덱스를 넣는다.
        # 만약 false라면, or 뒤의 i (부모 노드의 인덱스 값) 의 값을 largest에 넣는다.
        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

        if i is not largest:
            self.data[i], self.data[largest] = self.data[largest], self.data[i] # 자리 교체
            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)]:
            self.data[i] = self.data[self.parent(i)]
            i = self.parent(i)
        self.data[i] = item
    
l1 = [3,2,5,1,7,8,2]

h = Heapify(l1)
if h.extract_max() == 8:
    print('테스트 통과!')

 

위 코드에서 구현된 최대 힙에서 최댓값 추출 및 삭제 과정은 다음과 같다.

 

  1. 힙의 루트 노드 값을 밖으로 먼저 빼내 저장한 다음, 마지막 노드의 값을 대입한 후 마지막 노드를 삭제한다.

    2. 재정렬해준다.

우선순위 큐

우선순위 큐 (priority queue) 는 일반 스택과 큐와 비슷한 추상 데이터 타입이지만 각 항목마다 연관된 우선순위가 있다. 만약 두 항목의 우선순위가 같으면 큐의 순서를 따른다. 우선순위 큐는 힙을 사용하여 구현한다.

 

이제 heapq 모듈을 사용해서 우선순위 큐 클래스를 구현해보자. 숫자가 클 수록 우선순위가 높은 것이다.

 

import heapq

class PriorityQueue(object):
    def __init__(self):
        self._queue = []
        self._index = 0
    
    def push(self, item, priority):
        # 작은 값부터 반환하기 때문에 priority가 높을 수록 인덱스 내에 들어가는 값이 작아야 한다.
        # 이를 -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)

q = PriorityQueue()

q.push(Item('most prior'), 3)
q.push(Item('prior'), 2)
q.push(Item('not prior'), 1)

print(q.pop())
print(q.pop())
print(q.pop())

 

연결 리스트 

연결 리스트 (linked list) 는 값과 다음 노드에 대한 포인터 (참조) 가 포함된 노드로 이루어진 선형 리스트다. 마지막 노드는 null 값 (파이썬에선 None) 을 갖는다. 또한 연결 리스트로 스택 (새 항목을 헤드, head에 추가하는 방식) 과 큐 (새 항목을 테일, tail에 추가하는 방식) 를 구현할 수 있다.

 

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

d = Node('d')
c = Node('c', d)
b = Node('b', c)
a = Node('a', b) # 선형 노드, a가 최상위 노드인 식

print(a.getData())
print(a.getNext().getData()) # 포인터의 값 출력

 

연결 리스트의 크기는 동적일 수 있다. 따라서 런타임에 저장할 항목의 수를 알 수 없을 때 유용하다. 연결 리스트의 단순 삽입 시간 복잡도는 O(1) 이다. 그러나 특정 인덱스에 항목을 삽입할 때의 시간 복잡도는 O(n) 이다.

 

연결 리스트는 순차적으로 항목을 검색한다. 따라서 검색 및 삭제의 시간 복잡도는 O(n) 이다. 연결 리스트를 뒤부터 순회하거나 정렬하는 최악의 경우, 시간 복잡도는 O(n^2)이다. 만약 어떤 노드의 포인터를 알고 있을 때 그 노드를 삭제한다면, 삭제 시간 복잡도는 O(1)이 될 수 있다. 이는 해당 노드의 값에 다음 노드의 값을 할당하고 해당 노드의 포인터는 다음 다음 노드를 가리키게 하면 되기 때문이다.

 

해시 테이블

해시 테이블 (hash table) 은 키 (key) 를 값 (value) 에 연결하여 하나의 키가 0 또는 1개의 값과 연관된다. 또한, 각 키는 해시 함수 (hash functiono) 를 계산할 수 있어야 한다. 해시 테이블은 해시 버킷 (hash bucket) 의 배열로 구성된다. 예를 들어, 해시 값이 42이고 5개의 버킷이 있는 경우 나머지 연산 (mod) 을 사용하여 버킷 2(= 42 mod 5) 에 매핑한다.

 

허나 두 개의 키가 동일한 버킷에 해시될 때 문제가 발생한다. 이를 해시 충돌 (hash collision) 이라고 하는데, 이를 처리하는 한 가지 방법은 각 버킷에 대해 키-값 쌍의 연결 리스트를 저장하는 것이다.

 

해시 테이블의 조회, 삽입, 삭제의 시간 복잡도는 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([])
    
    def _find(self, item):
        return item % self.size # mod
    
    def _add(self, item):
        index = self._find(item) # slot index
        self.slots[index].append(item)

    def _delete(self,item):
        index = self._find(item)
        self.slots[index].remove(item)

    def _print(self):
        for i in range(self.size):
            print("slot ({0})".format(i))
            print(self.slots[i])
    
H1 = HashTableLL(3)
for i in range(20):
    H1._add(i)

H1._print()
H1._delete(0)
H1._delete(1)
H1._delete(2)

print('\n0, 1, 2 삭제\n')

H1._print()

 

결과

 

slot (0)
[0, 3, 6, 9, 12, 15, 18]
slot (1)
[1, 4, 7, 10, 13, 16, 19]
slot (2)
[2, 5, 8, 11, 14, 17]

0, 1, 2 삭제

slot (0)
[3, 6, 9, 12, 15, 18]
slot (1)
[4, 7, 10, 13, 16, 19]
slot (2)
[5, 8, 11, 14, 17]

 

출처

파이썬 자료구조와 알고리즘 - 한빛미디어, 미아 스타인

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html