큐, 덱, 이진 탐색 트리, 우선 순위 큐, 그래프

 

 

• 자료구조는 이틀만에 끝나네요
• 벌써 6일차입니다ㅎㅎ
• 그럼 오늘도 출발~!

 

 

 

---

 

 

 

 

1. 큐 (Queue)

• 큐(queue)는 먼저 삽입된 데이터가 먼저 추출되는 자료구조(data structure)다
  예시) 게임 대기 큐는 먼저 대기한 사람이 먼저 게임에 매칭된다

1-1. 연결 리스트로 큐 구현하기

• 큐를 연결 리스트로 구현하면, 삽입과 삭제에 있어서 𝑂(1)을 보장할 수 있다
• 연결 리스트로 구현할 때는 머리(head)와 꼬리(tail) 두 개의 포인터를 가진다
• 머리(head) : 남아있는 원소 중 가장 먼저 들어 온 데이터를 가리키는 포인터
• 꼬리(tail) : 남아있는 원소 중 가장 마지막에 들어 온 데이터를 가리키는 포인터

1-2. 파이썬으로 큐 구현해보기

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Queue:
    def __init__(self):
        self.head = None
        self.tail = None

    def enqueue(self, data):
        node = Node(data)
        if self.head == None:
            self.head = node
            self.tail = node
        # 꼬리(tail) 위치에 새로운 노드 삽입
        else:
            self.tail.next = node
            self.tail = self.tail.next

    def dequeue(self):
        if self.head == None:
            return None

        # 머리(head) 위치에서 노드 꺼내기
        data = self.head.data
        self.head = self.head.next

        return data

    def show(self):
        cur = self.head
        while cur:
            print(cur.data, end=" ")
            cur = cur.next


queue = Queue()
data_list = [3, 5, 9, 8, 5, 6, 1, 7]

for data in data_list:
    queue.enqueue(data)

print("\n전체 노드 출력:", end=" ")
queue.show()

print("\n[원소 삭제]")
print(queue.dequeue())
print(queue.dequeue())
print(queue.dequeue())

print("[원소 삽입]")
queue.enqueue(2)
queue.enqueue(5)
queue.enqueue(3)

print("전체 노드 출력:", end=" ")
queue.show()

• Python의 리스트 자료형을 사용하여 큐를 구현할 수도 있지만 비효율적이다
• 큐(queue)의 구현 방식에 따른 연산 속도를 비교

import time

data_list = [i for i in range(100000)]

start_time = time.time()

queue = []
for data in data_list:
    queue.append(data)
while queue:
    queue.pop(0)

print(f"Elapsed time: {time.time() - start_time} seconds.")
print(queue)

start_time = time.time()

queue = Queue()
for data in data_list:
    queue.enqueue(data)
while queue.head != None:
    queue.dequeue()

print(f"Elapsed time: {time.time() - start_time} seconds.")
queue.show()

• 4배 가량 속도 차이가 나는 것을 확인할 수 있다

2. 덱 (Deque)

• 덱은 스택(stack)과 큐(queue)의 기능을 모두 가지고 있다
• 포인터 변수가 더 많이 필요하기 때문에, 메모리는 상대적으로 더 많이 필요하다
• Python에서는 큐(queue)의 기능이 필요할 때 간단히 덱(deque)을 사용한다
• 데이터의 삭제와 삽입 모두에서 𝑂(1)의 시간 복잡도가 소요된다
• 덱에서는 좌측 또는 우측 양 끝에서 자유롭게 데이터를 삽입하고 삭제할 수 있다

2-1. 파이썬의 덱(Deque) 라이브러리

• Python에서는 덱(deque) 라이브러리를 사용할 수 있다
• 아래의 모든 메서드는 최악의 경우 시간 복잡도 𝑂(1)을 보장한다
• 우측 삽입: 𝑎𝑝𝑝𝑒𝑛𝑑() 
• 좌측 삽입: 𝑎𝑝𝑝𝑒𝑛𝑑𝑙𝑒𝑓𝑡() 
• 우측 추출: 𝑝𝑜𝑝()
• 좌측 추출: 𝑝𝑜𝑝𝑙𝑒𝑓𝑡()

2-2. 연결 리스트로 덱 구현하기

• 덱(deque)을 연결 리스트로 구현하면, 삽입과 삭제에 있어서 𝑂(1)을 보장할 수 있다
• 연결 리스트로 구현할 때는 앞(front)과 뒤(rear) 두 개의 포인터를 가진다
• 앞(front) : 가장 좌측에 있는 데이터를 가리키는 포인터
• 뒤(rear) : 가장 우측에 있는 데이터를 가리키는 포인터

2-3. Python에서 덱(Deque)을 사용하는 경우

• 기본적인 Python의 리스트 자료형은 큐(queue)의 기능을 제공하지 않는다
• 가능하다면 Python에서 제공하는 덱(deque) 라이브러리를 사용한다
• 큐(queue)의 기능이 필요할 때는 덱 라이브러리를 사용하는 것을 추천한다
• 삽입과 삭제에 대하여 모두 시간 복잡도 𝑂(1)이 요구된다

2-4. 파이썬으로 덱(Deque) 구현해보기

from collections import deque


d = deque()
arr = [5, 6, 7, 8]
for x in arr:
    d.append(x)
arr = [4, 3, 2, 1]
for x in arr:
    d.appendleft(x)
print(d)

while d:
    print(d.popleft())

arr = [1, 2, 3, 4, 5, 6, 7, 8]
for x in arr:
    d.appendleft(x)
print(d)

while True:
    print(d.pop())
    if not d:
        break
    print(d.popleft())
    if not d:
        break

• 연결 리스트를 이용한 덱 구현

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None


class Deque:
    def __init__(self):
        self.front = None
        self.rear = None
        self.size = 0

    def appendleft(self, data):
        node = Node(data)
        if self.front == None:
            self.front = node
            self.rear = node
        else:
            node.next = self.front
            self.front.prev = node
            self.front = node
        self.size += 1

    def append(self, data):
        node = Node(data)
        if self.rear == None:
            self.front = node
            self.rear = node
        else:
            node.prev = self.rear
            self.rear.next = node
            self.rear = node
        self.size += 1

    def popleft(self):
        if self.size == 0:
            return None
        # 앞에서 노드 꺼내기
        data = self.front.data
        self.front = self.front.next
        # 삭제로 인해 노드가 하나도 없는 경우
        if self.front == None:
            self.rear = None
        else:
            self.front.prev = None
        self.size -= 1
        return data

    def pop(self):
        if self.size == 0:
            return None
        # 뒤에서 노드 꺼내기
        data = self.rear.data
        self.rear = self.rear.prev
        # 삭제로 인해 노드가 하나도 없는 경우
        if self.rear == None:
            self.front = None
        else:
            self.rear.next = None
        self.size -= 1
        return data

    def front(self):
        if self.size == 0:
            return None
        return self.front.data

    def rear(self):
        if self.size == 0:
            return None
        return self.rear.data

    # 앞에서부터 원소 출력
    def show(self):
        cur = self.front
        while cur:
            print(cur.data, end=" ")
            cur = cur.next


d = Deque()
arr = [5, 6, 7, 8]
for x in arr:
    d.append(x)
arr = [4, 3, 2, 1]
for x in arr:
    d.appendleft(x)
d.show()

print()
while d.size != 0:
    print(d.popleft())

arr = [1, 2, 3, 4, 5, 6, 7, 8]
for x in arr:
    d.appendleft(x)
d.show()

print()
while True:
    print(d.pop())
    if d.size == 0:
        break
    print(d.popleft())
    if d.size == 0:
        break

3. 이진 탐색 트리

3-1. 트리 (Tree)

• 트리는 계층적인 구조를 표현할 때 사용할 수 있는 자료구조다

• 루트 노드(root node): 부모가 없는 최상위 노드
• 단말 노드(leaf node): 자식이 없는 노드
• 트리에서는 부모와 자식 관계라는 것이 있다
• 형제 관계란 같은 부모를 가지는 관계

• 트리에는 깊이라는 용어가 있다
• 깊이(depth): 루트 노드에서의 길이(length)
• 길이란 출발 노드에서 목적지 노드까지 거쳐야 하는 간선의 수를 의미한다
• 트리의 높이(height)은 루트 노드에서 가장 깊은 노드까지의 길이를 의미한다

3-2. 이진 탐색 트리 (Binary Search Tree)

• 이진 트리는 최대 2개의 자식을 가질 수 있는 트리를 말한다
• 다수의 데이터를 관리(조회, 저장, 삭제)하기 위한 가장 기본적인 자료구조 중 하나다
• 이진 탐색 트리의 특징
  • 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
  • 특정한 노드의 키(key) 값보다 그 왼쪽 자식 노드의 키(key) 값이 더 작다
  • 특정한 노드의 키(key) 값보다 그 오른쪽 자식 노드의 키(key) 값이 더 크다
  • 특정한 노드의 왼쪽 서브 트리, 오른쪽 서브 트리 모두 이진 탐색 트리다

3-2-1. 이진 탐색 트리 – 삽입 연산

• 루트 노드에서 출발하여 아래쪽으로 내려오면서, 삽입할 위치를 찾는다
• 삽입할 노드의 키(key)가 작으면 왼쪽으로, 삽입할 노드의 키(key)가 크면 오른쪽으로 삽입

3-2-2. 이진 탐색 트리 – 조회 연산

• 루트 노드에서 출발하여 아래쪽으로 내려오면서, 찾고자 하는 원소를 조회한다
• 삽입할 노드의 키(key)가 작으면 왼쪽으로, 삽입할 노드의 키(key)가 크면 오른쪽으로 조회

27 찾기

3-2-3. 이진 탐색 트리 – 삭제 연산

• 이진 탐색 트리에서의 삭제 연산은 세가지의 경우의 수를 가지고 실행한다
  1. 왼쪽 자식이 없는 경우 → 오른쪽 자식으로 대체
  2. 오른쪽 자식이 없는 경우 → 왼쪽 자식으로 대체
  3. 왼쪽, 오른쪽이 모두 있는 경우 → 오른쪽 서브 트리에서 가장 작은 노드로 대체

왼쪽, 오른쪽이 모두 있는 경우

3-3. 트리의 순회 (traversal)

• 트리에 포함되어 있는 정보를 모두 출력하고자 할 때 순회(traversal)를 사용할 수 있다
• 트리의 모든 노드를 특정한 순서(조건)에 따라서 방문하는 방법을 순회(traversal)라고 한다
  1. 전위 순회(pre-order traverse): 루트 방문 → 왼쪽 자식 방문 → 오른쪽 자식 방문 
  2. 중위 순회(in-order traverse): 왼쪽 자식 방문 → 루트 방문 → 오른쪽 자식 방문
  3. 후위 순회(post-order traverse): 왼쪽 자식 방문 → 오른쪽 자식 방문 → 루트 방문
  4. 레벨 순회(Level Order Traversal): 낮은 레벨(루트)부터 높은 레벨까지 순차적으로 방문한다, 너비 우선 탐색(BST)

3-4. 편향 이진 트리 (Skewed Binary Tree)

• 편향 이진 트리는 다음의 두 가지 속성을 가진다
  1. 같은 높이의 이진 트리 중 최소 개수의 노드 개수를 가진다
  2. 왼쪽 혹은 오른쪽으로 한 방향에 대한 서브 트리를 가진다

3-5. 이진 탐색 트리의 시간 복잡도

• 노드의 개수가 𝑁개일 때, 시간 복잡도는 다음과 같다
• 트리의 높이(height)을 𝐻라고 할 때, 엄밀한 시간 복잡도는 𝑂(𝐻)다
• 이상적인 경우 𝐻 = $log_{2}N$로 볼 수 있다
• 하지만 최악의 경우(편향된 경우) 𝐻 = 𝑁로 볼 수 있다

	조회	삽입	삭제	수정
균형 잡힌 이진 탐색 트리	𝑂(𝑙𝑜𝑔𝑁)	𝑂(𝑙𝑜𝑔𝑁)	𝑂(𝑙𝑜𝑔𝑁)	𝑂(𝑙𝑜𝑔𝑁)
편향 이진 탐색 트리	𝑂(𝑁)	𝑂(𝑁)	𝑂(𝑁)	𝑂(𝑁)

3-6. 균형 잡힌 트리: AVL 트리 (Adelson, Velski & Landis Tree)

• 이진 탐색 트리는 편향 트리가 될 수 있으므로, 최악의 경우 𝑂(𝑁)을 요구한다
• 반면에 AVL 트리는 균형이 갖춰진 이진 트리다
• 간단한 구현 과정으로 완전 이진 트리에 가까운 형태를 유지하도록 한다
• AVL 트리는 다음 4가지를 통해 트리를 재편성한다
  1. Left rotation
  2. Right rotation
  3. Left-Right rotation
  4. Right-Left rotation

3-7. 파이썬으로 이진 탐색 트리 구현해보기

from collections import deque


class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None


class BinarySearchTree:
    def __init__(self):
        self.root = None

    def search(self, node, key):
        return self._search(self.root, key)

    def _search(self, node, key):
        if node is None or node.key == key:
            return node

        # 현재 노드의 key보다 작은 경우
        if node.key > key:
            return self._search(node.left, key)
        # 현재 노드의 key보다 큰 경우
        elif node.key < key:
            return self._search(node.right, key)

    def insert(self, key):
        self.root = self._insert(self.root, key)

    def _insert(self, node, key):
        if node is None:
            return Node(key)

        # 현재 노드의 key보다 작은 경우
        if node.key > key:
            node.left = self._insert(node.left, key)
        # 현재 노드의 key보다 큰 경우
        elif node.key < key:
            node.right = self._insert(node.right, key)

        return node

    def delete(self, key):
        self.root = self._delete(self.root, key)

    def _delete(self, node, key):
        if node is None:
            return None

        # 현재 노드의 key보다 작은 경우
        if node.key > key:
            node.left = self._delete(node.left, key)
        # 현재 노드의 key보다 큰 경우
        elif node.key < key:
            node.right = self._delete(node.right, key)
        # 삭제할 노드를 찾은 경우
        else:
            # 왼쪽 자식이 없는 경우
            if node.left is None:
                return node.right
            # 오른쪽 자식이 없는 경우
            elif node.right is None:
                return node.left
            # 왼쪽과 오른쪽 자식 모두 있는 경우
            node.key = self._get_min(node.right)
            node.right = self._delete(node.right, node.key)

        return node

    def _get_min(self, node):
        key = node.key
        while node.left:
            key = node.left.key
            node = node.left
        return key

    def preorder(self):
        self._preorder(self.root)

    def _preorder(self, node):
        if node:
            print(node.key, end=' ')
            self._preorder(node.left)
            self._preorder(node.right)

    def inorder(self):
        self._inorder(self.root)

    def _inorder(self, node):
        if node:
            self._inorder(node.left)
            print(node.key, end=' ')
            self._inorder(node.right)

    def postorder(self):
        self._postorder(self.root)

    def _postorder(self, node):
        if node:
            self._postorder(node.left)
            self._postorder(node.right)
            print(node.key, end=' ')

    def levelorder(self):
        return self._levelorder(self.root)

    def _levelorder(self, node):
        if node is None:
            return

        result = []

        queue = deque()
        queue.append((0, node))  # (level, node)

        while queue:
            level, node = queue.popleft()
            if node:
                result.append((level, node.key))
                queue.append((level + 1, node.left))
                queue.append((level + 1, node.right))

        for level, key in result:
            print(f"level: {level}, key: {key}")

    def to_list(self):
        return self._to_list(self.root)

    def _to_list(self, node):
        if node is None:
            return []
        return self._to_list(node.left) + [node.key] + self._to_list(
            node.right)


arr = [7, 4, 5, 9, 6, 3, 2, 8]
bst = BinarySearchTree()
for x in arr:
    bst.insert(x)
print('전위 순회:', end=' ')
bst.preorder()
print('\n중위 순회:', end=' ')
bst.inorder()
print('\n후위 순회:', end=' ')
bst.postorder()
print('\n[레벨 순회]')
bst.levelorder()

bst.delete(7)
print('\n전위 순회:', end=' ')
bst.preorder()
print('\n중위 순회:', end=' ')
bst.inorder()
print('\n후위 순회:', end=' ')
bst.postorder()
print('\n[레벨 순회]')
bst.levelorder()

bst.delete(4)
print('\n전위 순회:', end=' ')
bst.preorder()
print('\n중위 순회:', end=' ')
bst.inorder()
print('\n후위 순회:', end=' ')
bst.postorder()
print('\n[레벨 순회]')
bst.levelorder()

bst.delete(3)
print('\n전위 순회:', end=' ')
bst.preorder()
print('\n중위 순회:', end=' ')
bst.inorder()
print('\n후위 순회:', end=' ')
bst.postorder()
print('\n[레벨 순회]')
bst.levelorder()

print(bst.to_list())

4. 우선순위 큐 (Priority Queue)

• 우선순위 큐는 우선순위에 따라서 데이터를 추출하는 자료구조이다
• 우선순위 큐는 일반적으로 힙(heap)을 이용해 구현한다

4-1. 힙(Heap)의 시간 복잡도

우선 순위 큐 구현 방식	삽입 시간	삭제 시간
리스트 자료형	𝑂(1)	𝑂(𝑁)
힙 (Heap)	𝑂(𝑙𝑜𝑔𝑁)	𝑂(𝑙𝑜𝑔𝑁)

4-2. 힙 (heap)

• 힙(Heap)은 원소들 중에서 최댓값 혹은 최솟값을 빠르게 찾아내는 자료구조다
• 최대 힙(Max Heap): 값이 큰 원소부터 추출한다
• 최소 힙(Min Heap): 값이 작은 원소부터 추출한다
• 힙은 원소의 삽입과 삭제를 위해 𝑂(𝑙𝑜𝑔𝑁)의 수행 시간을 요구한다
• 단순한 𝑁개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일하다
• 이 경우 시간 복잡도는 𝑂(𝑁𝑙𝑜𝑔𝑁) 이다
• 힙은 완전 이진 트리 자료구조를 따른다
• 힙에서는 우선순위가 높은 노드가 루트(root)에 위치한다

4-3. 최대 힙 (Max Heap)

• 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크다
• 루트 노드가 가장 크며, 값이 큰 데이터가 우선순위를 가진다

4-4. 최소 힙 (min heap)

• 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작다
• 루트 노드가 가장 작으며, 값이 작은 데이터가 우선순위를 가진다

4-5. 최소 힙 구성 함수: Heapify

• Heapify 함수를 통해 최소 힙이 되도록 재편성할 수 있다
• 재편성할 때는 부모로 거슬러 올라가며, 부모보다 자신이 더 작은 경우에 위치를 교체한다 (상향식)

• 이런식으로 하면 새로운 원소가 삽입되었을 때 𝑂(𝑙𝑜𝑔𝑁)의 시간 복잡도로 힙 성질을 유지하도록 할 수 있다
• 최소 힙에서 원소를 제거할 때는 가장 마지막 노드가 루트 노드의 위치에 오도록 한 후에 Heapify 함수로 재편성한다
  → 가장 마지막 노드가 가장 크기 때문에 바꿔주고 재편성, 이 때는 거슬러 올라가는 것이 아닌 하향식
  → 이런식으로 하면 새로운 원소가 삭제되었을 때 𝑂(𝑙𝑜𝑔𝑁)의 시간 복잡도로 힙 성질을 유지하도록 할 수 있다

4-6. 파이썬의 힙(Heap) 라이브러리

• 파이썬에서는 힙(Heap) 라이브러리를 제공한다
• ℎ𝑒𝑎𝑝𝑞 라이브러리의 삽입 및 삭제에 대한 시간 복잡도는 모두 𝑂(𝑙𝑜𝑔𝑁)이다

4-6-1. heapq 라이브러리 – 힙 초기화

import heapq

heap = []
print(heap)
# 실행 결과 : []

4-6-2. heapq 라이브러리 – 삽입(push)과 추출(pop)

• 원소의 삽입: ℎ𝑒𝑎𝑝𝑝𝑢𝑠ℎ() 메서드
• 원소의 추출: ℎ𝑒𝑎𝑝𝑝𝑜𝑝() 메서드

import heapq

heap = []

heapq.heappush(heap, 7)
heapq.heappush(heap, 4)
heapq.heappush(heap, 5)
heapq.heappush(heap, 8)

while heap:
	element = heapq.heappop(heap)
	print(element, end=" ")
# 실행 결과 : 4 5 7 8

4-6-3. heapq 라이브러리 – 최솟값 구하기

import heapq

heap = []

heapq.heappush(heap, 7)
heapq.heappush(heap, 4)
heapq.heappush(heap, 5)
heapq.heappush(heap, 8)

print(heap[0])
#실행 결과 : 4

4-6-4. heapq 라이브러리 – 리스트를 힙으로 변환

• ℎ𝑒𝑎𝑝𝑝𝑢𝑠ℎ() 메서드를 이용해 하나씩 원소를 삽입하지 않을 수 있다
• ℎ𝑒𝑎𝑝𝑖𝑓𝑦() 메서드는 새로운 리스트를 반환하지 않고, 리스트 내부를 직접 수정한다

import heapq

heap = [9, 1, 5, 4, 3, 8, 7]
heapq.heapify(heap)

while heap:
	element = heapq.heappop(heap)
	print(element, end=" ")
# 실행 결과 : 1 3 4 5 7 8 9

4-6-5. heapq 라이브러리 – 최대 힙 (Max Heap)

• 파이썬의 heapq 라이브러리는 기본적으로 최소 힙 기능을 제공한다
• 최대 힙을 위해서는 삽입과 추출할 때 키(key)에 음수(-) 부호를 취한다

import heapq

arr = [9, 1, 5, 4, 3, 8, 7]
heap = []

for x in arr:
	heapq.heappush(heap, -x)
    
while heap:
	x = -heapq.heappop(heap)
	print(x, end=" ")
# 실행 결과 : 9 8 7 5 4 3 1

4-7. 힙 활용 예시

4-7-1.  힙 정렬 (Heap Sort)

• 단순히 힙에 원소를 넣었다가 꺼내는 것 만으로도 정렬을 수행할 수 있다

import heapq

def heap_sort(arr):
	heap = []
	for x in arr:
		heapq.heappush(heap, x)
	result = []
	while heap:
		x = heapq.heappop(heap)
		result.append(x)
	return result
    
print(heap_sort([9, 1, 5, 4, 3, 8, 7]))
# 실행 결과 : [1, 3, 4, 5, 7, 8, 9]

4-7-2. N번째로 작은 값

• 최소 힙이나 최대 힙을 사용하여 𝑛번째로 작은 값이나 𝑛번째로 큰 값을 얻을 수 있다
• 힙(heap)을 만든 뒤에 추출(pop) 함수를 𝑛번 호출한다

import heapq

def n_smallest(n, arr):
	heap = []
	for x in arr:
		heapq.heappush(heap, x)
	result = None
	for _ in range(n):
		result = heapq.heappop(heap)
	return result
    
arr = [9, 1, 5, 4, 3, 8, 7]
print(n_smallest(3, arr))
# 실행 결과 : 4

• 파이썬에서는 𝑁번째로 작은 값을 구하는 메서드를 제공한다
• 𝑛𝑠𝑚𝑎𝑙𝑙𝑒𝑠𝑡() 메서드는 가장 작은 𝑛개의 값을 반환한다.

import heapq

arr = [9, 1, 5, 4, 3, 8, 7]
result = heapq.nsmallest(3, arr)
print(result[-1])
# 실행 결과 : 4

4-7-3. N번째로 큰 값

• 파이썬에서는 𝑁번째로 큰 값을 구하는 메서드를 제공한다
• 𝑛𝑙𝑎𝑟𝑔𝑒𝑠𝑡() 메서드는 가장 큰 𝑛개의 값을 반환한다

import heapq

arr = [9, 1, 5, 4, 3, 8, 7]
result = heapq.nlargest(3, arr)
print(result[-1])
# 실행 결과 : 7

4-8. 파이썬으로 힙 구현하기

class Heap(object):
    def __init__(self):
        # 첫번째 원소는 사용하지 않음
        self.arr = [None]

    # 원소 삽입(push)
    def push(self, x):
        # 마지막 위치에 원소를 삽입
        self.arr.append(x)
        # 첫 원소인 경우 종료
        if len(self.arr) == 2:
            return
        # 값의 크기를 비교하며 부모를 타고 올라감
        i = len(self.arr) - 1
        while True:
            parent = i // 2
            # 작은 값을 부모 쪽으로 계속 이동
            if 1 <= parent and self.arr[parent] > self.arr[i]:
                self.arr[parent], self.arr[i] = self.arr[i], self.arr[parent]
                i = parent
            else:
                break

    # 원소 추출(pop)
    def pop(self):
        # 마지막 원소
        i = len(self.arr) - 1
        # 남은 원소가 없다면 종료
        if i < 1:
            return None
        # 루트 원소와 마지막 원소를 교체하여, 마지막 원소 추출
        self.arr[1], self.arr[i] = self.arr[i], self.arr[1]
        result = self.arr.pop()
        # 루트(root)에서부터 원소 정렬
        self.heapify()
        return result

    # 루트(root)에서부터 자식 방향으로 내려가며 재정렬
    def heapify(self):
        # 남은 원소가 1개 이하라면 종료
        if len(self.arr) <= 2:
            return
        # 루트 원소
        i = 1
        while True:
            # 왼쪽 자식
            child = 2 * i
            # 왼쪽 자식과 오른쪽 자식 중 더 작은 것을 선택
            if child + 1 < len(self.arr):
                if self.arr[child] > self.arr[child + 1]:
                    child += 1
            # 더 이상 자식이 없거나, 적절한 위치를 찾은 경우
            if child >= len(self.arr) or self.arr[child] > self.arr[i]:
                break
            # 원소를 교체하며, 자식 방향으로 내려가기
            self.arr[i], self.arr[child] = self.arr[child], self.arr[i]
            i = child

arr = [9, 1, 5, 4, 3, 8, 7]
heap = Heap()

for x in arr:
    heap.push(x)

while True:
    x = heap.pop()
    if x == None:
        break
    print(x, end=" ")

• 힙 정렬 속도 측정해보기

import random
import time


# N개의 무작위 데이터 생성
arr = []
n = 100000
for _ in range(n):
	arr.append(random.randint(0, 1000000))

# 시간 측정 시작
start_time = time.time()

# 힙에 모든 원소 삽입
heap = Heap()
for x in arr:
	heap.push(x)

# 힙에서 모든 원소 추출
result = []
while True:
	x = heap.pop()
	if x == None:
		break
	result.append(x)

# 시간 측정 종료
print(f"Elapsed time: {time.time() - start_time} seconds.")

# 오름차순 정렬 여부 확인
ascending = True
for i in range(n - 1):
	if result[i] > result[i + 1]:
		ascending = False
print("Sorted:", ascending)

# 가장 작은 5개 원소와 가장 큰 5개 원소 출력
print(result[:5])
print(result[-5:])

5. 그래프 (Graph)

• 그래프(graph)란 사물을 정점(vertex)과 간선(edge)으로 나타내기 위한 도구다
• 그래프는 두 가지 방식으로 구현할 수 있다
  1. 인접 행렬(adjacency matrix): 2차원 배열을 사용하는 방식
  2. 인접 리스트(adjacency list): 연결 리스트를 이용하는 방식
• 그래프 종류
  1. 무방향 무가중치 그래프 : 모든 간선이 방향성을 가지지 않는 그래프를 무방향 그래프
  2. 무가중치 그래프 : 모든 간선에 가중치가 없는 그래프
  3. 방향 그래프 : 모든 간선이 방향을 가지는 그래프를 방향 그래프
  4. 가중치 그래프 : 모든 간선에 가중치가 있는 그래프

5-1. 인접 행렬 (Adjacency Matrix)

• 인접 행렬(adjacency matrix)에서는 그래프를 2차원 배열로 표현한다

5-1-1. 인접 행렬 - 무방향 무가중치 그래프

graph = [
[0, 1, 1, 0],
[1, 0, 1, 0],
[1, 1, 0, 1],
[0, 0, 1, 0]
]

5-1-2. 인접 행렬 - 방향 가중치 그래프

graph = [
[0, 0, 7, 0],
[3, 0, 8, 0],
[0, 8, 0, 0],
[0, 0, 4, 0]
]

5-2. 인접 리스트 (Adjacency List)

• 인접 리스트(adjacency list)에서는 그래프를 리스트로 표현한다

5-2-1. 인접 리스트 - 무방향 무가중치 그래프

graph = [
[1, 2],
[0, 2],
[0, 1, 3],
[2]
]

5-2-2. 인접 리스트 - 방향 가중치 그래프

graph = [
[(2, 7)],
[(0, 3), (2, 8)],
[(1, 8)],
[(2, 4)]
]

5-3. 그래프의 시간 복잡도

1. 인접 행렬: 모든 정점들의 연결 여부를 저장해 $O(V^{2})$의 공간을 요구한다
   • 공간 효율성이 떨어지지만, 두 노드의 연결 여부를 𝑂(1)에 확인할 수 있다
2. 인접 리스트: 연결된 간선의 정보만을 저장하여 𝑂(𝑉 + 𝐸)의 공간을 요구한다
   • 공간 효율성이 우수하지만, 두 노드의 연결 여부를 확인하기 위해 𝑂(𝑉)의 시간이 필요하다

	필요한 메모리	연결 여부 확인
인접 행렬	$O(V^{2})$	𝑂(1)
인접 리스트	𝑂(𝑉 + 𝐸)	𝑂(𝑉)

5-4. 인접 행렬 vs. 인접 리스트

• 최단 경로 알고리즘을 구현할 때, 어떤 자료구조가 유용할까?
• 각각 근처의 노드와 연결되어 있는 경우가 많으므로, 간선 개수가 적어 인접 리스트가 유리하다

 

 

 

 

 

 

---