[DEV] 2주차. 자료구조/알고리즘(3)

1. Queue

• 자료를 보관할 수 있는 (선형) 구조
• 선입선출 구조 (FIFO)
  • 한 쪽 끝에서 밀어 넣는 연산: 인큐(enqueue) 연산
  • 반대 쪽에서 뽑아 꺼내는 연산: 디큐(dequeue) 연산
  • 들어간 순서와 동일한 순서로 데이터가 꺼내짐

2. 큐의 동작

• 빈 큐 Q = Queue()
• 데이터 원소 A를 큐에 추가 Q.enqueue(A)
• 데이터 원소 B를 큐에 추가 Q.enqueue(B)
• 데이터 원소 꺼내기 r1 = Q.dequeue()
  • r1 == A
• 데이터 원소 또 꺼내기 r2 = Q.dequeue()
  • r2 == B

3. 큐의 추상적 자료구조 구현

0) 연산 정의

• size() : 현재 큐에 들어 있는 데이터 원소의 수 구함
• isEmpty() : 현재 큐가 비어있는지 판단
• enqueue(x) : 데이터 원소 x를 큐에 추가
• dequeue(x) : 큐의 맨 앞에 저장된 데이터 원소 제거 + 반환
• peek() : 큐의 맨 앞에 저장된 데이터 원소 반환 (제거하지 않음)

1) 배열을 이용하여 구현

• list

class ArrayQueue:
    def __init__(self):
        self.data = []
    
    def size(self):
        return len(self.data)

    def isEmpty():
        return self.size() == 0

    def enqueue(self, item):
        self.data.append(item)
    
    def dequeue(self):
        return self.data.pop(0)  # 0번 인덱스 pop, 뒤의 원소들은 앞으로 밀림 (1->0, 2->1)
    
    def peek(self):
        return self.data[0]

배열로 구현한 큐의 연산 복잡도

연산	복잡도
size()	O(1)
isEmpty()	O(1)
enqueue()	O(1)
dequeue()	O(n)
peek()	O(1)

dequeue 연산

• 0번 원소가 없어지고, 나머지 원소들이 앞으로 밀리기 때문
• 큐의 길이에 비례 -> 바람직하지 않음

2) 연결 리스트를 이용하여 구현

• 양방향 연결 리스트

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.size() + 1, node)

    def dequeue(self):
        return self.data.popAt(1)

    def peek(self):
        return self.data.getAt(1).data

3) Library

from pythonds.basic.queue import Queue

Q = Queue()

dir(Q)
# ['__doc__', '__init__', '__module__', 'dequeue', 'enqueue', 'isEmpty', 'items', 'size']

4. 큐의 활용

• 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로 일어나는 경우

• 자료를 생성하는 작업이 여러 곳에서 일어나는 경우

• 자료를 이용하는 작업이 여러 곳에서 일어나는 경우

• 자료를 생성하는 작업과 그 자료를 이용하는 작업이 양쪽 다 여러 곳에서 일어나는 경우

• 자료를 처리하여 새로운 자료를 생성하고 나중에 그 자료를 또 처리해야 하는 작업의 경우

5. 환형 큐 (Circular Queues)

• 정해진 개수의 저장 공간을 빙 돌려가며 이용
• 큐가 가득 차면 더이상 원소를 넣을 수 없음 -> 큐 길이를 기억하고 있어야 함

6. 환형 큐의 추상적 자료구조 구현

0) 연산 정의

• size() : 현재 큐에 들어 있는 데이터 원소의 수 구함
• isEmpty() : 현재 큐가 비어있는지 판단
• isFull() : 큐에 데이터 원소가 꽉 차 있는지를 판단
• enqueue(x) : 데이터 원소 x를 큐에 추가
• dequeue(x) : 큐의 맨 앞에 저장된 데이터 원소 제거 + 반환
• peek() : 큐의 맨 앞에 저장된 데이터 원소 반환 (제거하지 않음)

1) 배열로 구현한 환형 큐

• 정해진 길이 n의 리스트 확보
• enQueue(x) 할 때 rear += 1
  • rear는 마지막으로 추가된 원소의 인덱스
• deQueue() 할 때 front += 1
  • front는 큐에서 가장 앞에 있는 원소 (가장 먼저 들어간) 보다 하나 작은 인덱스

Q.enqueue(A)  # rear = A
Q.enqueue(B)  # rear = B
Q.enqueue(C)  # rear = C
Q.enqueue(D)  # rear = D
r1 = Q.dequeue()  # front = A, r1 = A, A는 무효한 데이터 취급
r2 = Q.dequeue()  # front = B, r2 = B, B는 무효한 데이터 취급
Q.enqueue(E)
Q.enqueue(F)  # rear = F, front는 1번 인덱스 가리키는 중
Q.enqueue(G)  # rear = G (0번 인덱스)
r3 = Q.dequeue()  # front = C, r3 = C

• front와 rear를 적절히 계산하여 배열을 환형으로 재활용

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 = 0 if self.rear+1 > self.maxCount-1 else self.rear+1
        self.data[self.rear] = x
        self.count += 1

    def dequeue(self):
        if self.size() == 0:
            raise IndexError('Queue empty')
        self.front = 0 if self.front+1 > self.maxCount-1 else self.front+1
        x = self.data[self.front]
        self.count -= 1
        return x

    def peek(self):
        if :
            raise IndexError('Queue empty')
        return self.data[0 if self.front+1 > self.maxCount-1 else self.front+1]

• 더 간편하게!
  • 0 if self.front+1 > self.maxCount-1 else self.front+1
  • (self.front+1) % self.maxCount

7. 우선순위 큐 (Priority Queue)

• 큐가 FIFO 방식을 따르지 않고, 원소들의 우선순위에 따라 큐에서 빠져나오는 방식
• 활용
  • 운영체제의 CPU 스케줄러

8. 우선순위 큐의 구현

• 두 가지 방법
  • Enqueue 할 때 우선순위 순서를 유지하도록
    • 더 유리!
  • Dequeue 할 때 우선순위 높은 것을 선택
• 두 가지 재료
  • 선형 배열 이용
  • 연결리스트 이용
    • 더 유리!

양방향 연결 리스트

from doublylinkedlist import Node, DoublyLinkedList

class PriorityQueue:
    def __init__(self, x):
        self.queue = DoublyLinkedList()

    # 작은 값이 우선순위 높음
    def enqueue(self, x):
        newNode = Node(x)
        curr =  self.queue.head  # 주의) getAt() 메서드 사용하지 않음
        while curr.next != self.queue.tail and curr.next.data > newNode.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

• enqueue while 문 조건
  • insertAfter 이기 때문에 curr의 다음이 tail이면 멈춰서 마지막에 insert해야 함
  • curr가 newNode보다 작다고 하면 그 작은 값보다 앞에 삽입되기 때문에 curr.next가 newNode보다 작을 때 멈춰야 함

9. 트리

• 정점(node)와 간선(edge)를 이용하여 데이터의 배치 형태를 추상화한 자료 구조

• 노드의 수준 (level)
  • root node = 레벨 0
  • root 노드부터 해당 노드까지 거치는 간선의 개수
• 트리의 높이/깊이 (height/depth)
  • 모든 노드들 중 최대 수준(level) + 1
• 노드의 차수 (degree)
  • 자식(서브트리)의 수

10. 이진 트리 (binary tree)

• 모든 노드의 차수가 2 이하인 트리
• 재귀적으로 정의할 수 있음
  • 빈 트리이거나 // 루트 노드 + 왼쪽 서브트리 + 오른쪽 서브트리
  • 이때 왼쪽, 오른쪽 서브트리 또한 빈 트리 / 이진 트리

1) 포화 이진 트리 (full binary tree)

• 모든 레벨에서 노드들이 모두 채워져 있는 이진 트리
• 높이가 $k$이고, 노드의 개수가 $2^k-1$인 이진 트리

2) 완전 이진 트리 (complete binary tree)

• 높이가 $k$인 완전 이진 트리
• 레벨 $k-2$까지는 모든 노드가 2개의 자식을 가진 포화 이진 트리
• 레벨 $k-1$에서는 왼쪽부터 노드가 순차적으로 채워져 있는 이진 트리

11. 이진 트리의 추상적 자료구조

1) 연산의 정의

• size() : 현재 트리에 포함되어 있는 노드의 수 구함
• depth() : 현재 트리의 깊이(높이)를 구함
• 순회 (traversal) : 정해진 순서로 노드를 방문해서 처리하는 연산

2) 이진 트리의 구현

• Node
  • data
  • left child
  • right child

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

• Tree
  • root

class BinaryTree:
    def __init__(self, r):
        self.root = r

• size()
  • 재귀적인 방법으로 쉽게 구할 수 있음
  • 전체 이진 트리의 size
    = left subtree size() + right subtree size() + 1 (자기자신)

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

    # 자기 자신이 root인 서브트리의 사이즈 구하는 멤버 메소드
    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 __init__(self, r):
        self.root = r

    def size(self):
        if self.root:
            return self.root.size()
        else: 
            return 0

• depth()
  • 재귀적인 방법으로 쉽게 구할 수 있음
  • 전체 이진 트리의 depth()
    = left subtree depth() + right subtree depth() 중 더 큰 것 + 1 (자기자신)

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

    # 자기 자신이 root인 서브트리의 사이즈 구하는 멤버 메소드
    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

    # 자기 자신을 root로 하는 서브트리의 depth
    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


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

12. 이진 트리의 순회 (traversal)

깊이 우선 순회 (depth first traversal)

중위 순회 (in-order)

• left subtree -> 자기 자신 -> right subtree

class Node:
    # 자기자신이 root인 서브트리에 대해 중위순회
    def 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 []

전위 순회 (pre-order)

• 자기 자신 -> left subtree -> right subtree

class Node:
    def preorder(self):
        traversal = []
        traversal.append(self.data)
        if self.left:
            traversal += self.left.preorder()
        if self.right:
            traversal += self.right.preorder()
        return traversal

class BinaryTree:
    def preorder(self):
        if self.root:
            return self.root.preorder()
        else:
            return []

후위 순회 (post-order)

• left subtree -> right subtree -> 자기 자신

class Node:
    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 postorder(self):
        if self.root:
            return self.root.postorder()
        else:
            return []

넓이 우선 순회 (breadth first traversal)

• level이 낮은 노드 우선 방문 (root부터 한 줄씩 아래로)
• 같은 레벨의 노드들 사이에는
  • 부모 노드의 방문 순서에 따라 방문
  • 왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문
• 이 방식에 재귀적 방법이 적합한가?
  • NO
• 한 노드를 방문했을 때
  • 나중에 방문할 노드들을 순서대로 기록해 두어야 함
  • Queue 이용!

알고리즘 설계

• root 노드 -> 큐에 넣고
  • 꺼내면서 왼쪽 자식 -> 오른쪽 자식 순서대로 enqueue
  • dequeue 하면서 왼쪽 자식 -> 오른쪽 자식 순서대로 enqueue
  • 반복!
• (초기화) traversal <- 빈 리스트, q <- 빈 큐
• 빈 트리가 아니면, root node를 q에 추가 (enqueue)
• q가 비어있지 않은 동안
  • node <- q 에서 원소 추출 (dequeue)
  • node 방문
  • node의 왼쪽, 오른쪽 자식이 있다면 이들을 q에 추가
• q가 빈 큐가 되면 모든 노드 방문 완료

구현

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

• traversal에 넣을 때 node.data !!! 로 넣어야 함!

13. 이진 탐색 트리 (Binary Search Trees)

• 모든 노드에 대해서
  • 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고
  • 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큰
    성질을 만족하는 이진 트리

• 중복되는 데이터 원소는 없는 것으로 가정

• 배열을 이용한 이진 탐색과 유사한 과정

정렬된 배열을 이진 탐색과 비교

• 장점
  • 데이터 원소의 추가, 삭제가 용이
• 단점
  • 공간 소요가 큼
  • 왼쪽, 오른쪽 자식을 기록해 두어야 하기 때문
  • 항상 $O(logn)$의 복잡도? [no]

14. 이진 탐색 트리의 추상적 자료 구조

1) 데이터 표현: 각 노드는 (key, value)의 쌍으로

• 키를 이용해서 검색 가능
• 보다 복잡한 데이터 레코드로 확장 가능

2) 연산의 정의

• insert(key, data) : 트리에 주어진 데이터 원소를 추가
• remove(key) : 특정 원소를 트리로부터 삭제
• lookup(key) : 특정 원소를 검색
• inorder() : 키의 순서대로 데이터 원소를 나열
• min(), max() : 최소 키, 최대 키를 가지는 원소를 각각 탐색

3) 초기화

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

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

4) inorder_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 []

5) min()

class Node:
    def min(self):
        if self.left:
            return self.left.min()
        else:
            return self

class BinSearchTree:
    def min(self):
        if self.root:
            return self.root.min()
        else:
            return None

6) max()

class Node:
    def max(self):
        if self.right:
            return self.right.max()
        else:
            return self

class BinSearchTree:
    def max(self):
        if self.root:
            return self.root.max()
        else:
            return None

7) lookup()

• 입력 인자: 찾으려는 대상 키
• 출력 인자: 찾은 노드와, 그것의 부모 노드

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:
            if self.right:
                return self.right.lookup(key, self)
            else:
                return None, None
        else:
            return self, parent

class BinSearchTree:
    def lookup(self, key):
        if self.root:
            return self.root.lookup(key)
        else:
            return None, None

8) insert()

• 입력 인자: 키, 데이터 원소
• 출력 인자: 없음

class Node:
    def insert(self, key, data):
        if key < self.key:
            if self.left:
                self.left.insert(key, data)
            else:
                self.left = Node(key, data)
        elif key > self.key:
            if self.right:
                self.right.insert(key, data)
            else:
                self.right = Node(key, data)
        else:
            raise KeyError('...')  # 중복된 원소는 없다고 가정

class BinSearchTree:
    def insert(self, key, data):
        if self.root:
            self.root.insert(key, data)
        else:
            self.root = Node(key, data)

15. 노드의 삭제, remove()

• key를 이용해서 노드를 찾음
  • 해당 키의 노드가 없으면 삭제할 것도 없음
  • 찾은 노드의 부모 노드도 알고 있어야 함
• 찾은 노드를 제거하고도 이진 탐색 트리 성질을 만족하도록 트리의 구조를 정리해야 함

인터페이스 설계

• 입력 인자: 키
• 출력 인자: 삭제한 경우 True, 해당 키의 노드가 없는 경우 False

class BinSearchTree:
    def remove(self, key):
        node, parnet = self.lookup(key)
        if node:
            ...
            return True
        else:
            return False

이진 탐색 트리 구조의 유지

삭제되는 노드가

• 말단(leaf) 노드인 경우
  • 그냥 그 노드를 없애면 됨
  • 부모 노드의 링크를 조정 (좌 / 우)
• 자식을 하나 가지고 있는 경우
  • 삭제되는 노드 자리에 그 자식을 대신 배치
  • 자식이 왼 / 오
  • 부모 노드의 링크를 조정 (좌 / 우)
• 자식을 둘 가지고 있는 경우
  • 삭제되는 노드보다 바로 다음 (큰) 키를 가지는 노드를 찾아 그 노드를 삭제되는 노드 자리에 대신 배치하고 이 노드를 대신 삭제
    • 오른쪽 서브트리에서 가장 왼쪽 키 (가장 작은) + 그 키의 부모 노드
  • (or) 바로 전 (작은) 키로 대신 배치해도 됨

자식 개수 세기

class Node:
    def countChildren(self):
        count = 0
        if self.left:
            count += 1
        if self.right:
            count += 1
        return count

16. 이진 탐색 트리가 별로 효율적이지 못한 경우

• 순서대로 키를 갖는 노드들을 insert -> 선형 탐색과 동등한 복잡도를 갖게 됨

17. 보다 나은 성능을 보이는 이진 탐색 트리들

• 높이의 균형을 유지함으로써 $O(logn)$의 탐색 복잡도 보장
• 삽입, 삭제 연산이 보다 복잡함
• AVL tree, Red-black tree

18. 힙 (Heaps)

• 이진 트리의 한 종류 (이진 힙 binary heap)
• 조건
  • root 노드가 언제나 최댓값 / 최솟값을 가짐
    • 최대 힙(max heap) / 최소 힙(min heap)
    • 특정한 노드에서 봤을 때 자신의 자식들보다 항상 크거나 작아야 함
  • 완전 이진트리여야 함

• 최대 힙의 예

• 재귀적으로도 정의됨
• 어느 노드를 루트로 하는 서브트리도 모두 최대 힙

19. 이진 탐색 트리와의 비교

비교	이진 탐색 트리	힙
원소들은 완전히 크기 순으로 정렬되어 있는가?	O	X
특정 키 값을 가지는 원소를 빠르게 검색할 수 있는가?	O	X
부가의 제약 조건은 어떤 것인가?		완전 이진 트리여야 함

20. 최대 힙의 추상적 자료구조

1) 연산의 정의

• __init__() : 빈 최대 힙 생성
• insert(item) : 새로운 원소 삽입
• remove() : 최대 원소 (root node) 반환 + 해당 노드 삭제

2) 배열을 이용한 이진 트리의 표현

• 노드 번호 m을 기준으로
  • 왼쪽 자식의 번호: 2 * m
  • 오른쪽 자식의 번호 : 2 * m + 1
  • 부모 노드의 번호 : m // 2
• 완전 이진 트리이므로 노드의 추가/삭제는 마지막 노드에서만 일어남
  -> 배열로 표현하기 나쁘지 않음

3) 초기화

class MaxHeap:
    def __init__(self):
        self.data = [None]  # 0번 인덱스는 버림

4) 최대 힙에 원소 삽입

• 트리의 마지막 자리에 새로운 원소를 임시로 저장

• 부모 노드와 키 값을 비교하여 위로, 위로 이동

• 복잡도
  • 원소의 개수가 $n$인 최대 힙에 새로운 원소 삽입
  • 부모 노드와의 대소 비교 최대 횟수: $log_2^n$
  • 최악 복잡도 $O(logn)$의 삽입 연산

class MaxHeap:
    def __init__(self):
        self.data = [None]

    def insert(self, item):
        self.data.append(item)
        i = len(self.data) - 1
        while i > 1:
            if self.data[i] > self.data[i//2]:
                self.data[i], self.data[i//2] = self.data[i//2], self.data[i]
                i = i//2
            else:
                break

• 부모 노드와 비교 해야 함 -> i//2 와 비교!

5) 최대 힙에서 원소의 삭제

• 항상 최댓값이 삭제 -> 루트 노드의 제거
• 트리 마지막 자리 노드를 임시로 루트 노드의 자리에 배치 -> 완전 이진 트리
• 자식 노드들과의 값 비교하여 아래로, 아래로 이동 -> 최대 힙
  • 자식은 두 개일 수 있음
  • 둘 중 더 큰 값을 기준으로 !
• 복잡도
  • 원소의 개수가 $n$인 최대 힙에서 최대 원소 삭제
  • 자식 노드들과의 대소 비교 최대 횟수: $2 * log_2^n$
  • 최악 복잡도 $O(logn)$의 삭제 연산

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)  # root 노드부터, 최대 힙 구조 유지
        else:
            data = None
        return data

    def maxHeapify(self, i):
        left = 2 * i
        right = 2 * i + 1
        greatest = i
        # 자신(i), left, right 중 최대 -> 인덱스를 greatest에 담음
        if left < len(self.data) and self.data[left] > self.data[i]:
            greatest = left
        if right < len(self.data) and self.data[right] > self.data[greatest]:
            greatest = right
        if greatest != i:
            self.data[i], self.data[greatest] = self.data[greatest], self.data[i]
            self.maxHeapify(greatest)

• i, left, right 중 최댓값을 변수에 담을 때 elif가 아니라 if
  -> left와 i를 먼저 비교하고, 그 중 최댓값과 right 를 비교하는 것

21. 최대/최소 힙의 응용

• 우선 순위 큐
  • enqueue 할 때 ‘느슨한 정렬’을 이루고 있도록 함 : $O(logn)$
  • dequeue 할 때 최댓값을 순서대로 추출 : $O(logn)$
• 힙 정렬
  • 정렬되지 않은 원소들을 아무 순서로나 최대 힙에 삽입 : $O(logn)$
  • 삽입이 끝나면, 힙이 비게 될 때까지 하나씩 삭제 : $O(logn)$
  • 원소들이 삭제된 순서가 원소들의 정렬 순서
  • 정렬 알고리즘의 복잡도 : $O(nlogn)$

힙 정렬 코드 구현

def heapsort(unsorted):
    H = MaxHeap()
    for item in unsorted:
        H.insert(item)

    sorted = []
    d = H.remove()
    while d:
        sorted.append(d)
        d = H.remove()

    return sorted