[데이터 엔지니어링 데브코스 2기] TIL-2주차-파트03 자료구조와 알고리즘

1. 큐(Queue)

큐는 자료를 보관할 수 있는 선형 구조로, FIFO(First In First Out)의 원칙을 따른다.

Queue의 활용 예) 운영 체제 시스템 내부, 네트워킹 시스템 내부 ..

1. 데이터의 생성과 추출 작업이 비동기적(asynchronous)으로 일어나는 경우
2. 데이터의 생성이 여러 곳에서 일어나는 경우
3. 데이터의 추출이 여러 곳에서 일어나는 경우

1) 큐의 Abstract Data Type 구현

1) 배열 : Python의 list
2) 연결 리스트 : Doubly Linked List

# 배열 queue
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]
        
# 연결 리스트 queue
from doublylinkedlist import *
class DoublyLinkedListQueue:
	def __init__(self):
    	self.data = DoublyLinkedList()
    
    def size(self):
    
    def isEmpty(self):
    
    # 한 쪽에서 데이터를 넣는다.
    def enqueue(self, item):
    
	# 반대 쪽에서 데이터를 꺼낸 후 반환한다.
    def dequeue(self):
    
	# 가장 앞의 데이터를 반환한다.
    def peek(self):
    

배열 queue의 연산별 시간 복잡도

연산 종류	시간 복잡도
size()	O(1)
isEmpty()	O(1)
enqueue(x)	O(1)
dequeue()	O(n)
peek()	O(1)

배열 queue의 경우 dequeue() 연산의 시간 복잡도가 O(n)으로 좋지 못하다. 따라서, 연결 리스트 queue를 활용한다.

2) 환형 큐(Circular Queue)

데이터의 최대 저장 개수를 지정한 후, queue를 돌아가며 이용.

class CircularQueue:
    def __init__(self, n):
        self.maxCount = n # 데이터의 최대 저장 개수 n.
        self.count = 0
        self.data = [None]*n
        self.front = -1 # 데이터를 추출하기 위한 pointer
        self.rear = -1 # 데이터를 입력하기 위한 pointer

    def size(self):

    def isEmpty(self):

    def isFull(self):

    def enqueue(self, x):
    
    def dequeue(self):
    
    def peek(self):

3) 우선순위 큐(Priority Queue)

FIFO 원칙이 아니라, 데이터의 우선 순위에 따라 데이터를 추출하는 자료 구조. ex) 운영체제의 CPU 스케쥴러

구현 방식)

1. enqueue()할 때, 우선 순위에 따라 queue에 데이터를 (비내림차순 등으로) 저장.
2. dequeue() 시, queue에서 가장 높은 우선 순위를 가진 데이터를 선택한 후 추출.

일반적으로 1번의 방법이 더 유리하다. 2의 방식으로 할 경우, 시간이 더 소모될 수 있다.

구현 자료구조)

1. 선형 배열 : 공간복잡도 good, 시간복잡도 bad.
2. 연결 리스트 : 중간 위치 삽입 및 삭제가 유연함. 따라서, 시간복잡도 good. 하지만, memory를 더 차지한다는 단점이 존재, 공간복잡도 bad.

from doublylinkedlist import *

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

    def size(self):

    def isEmpty(self):

    def isFull(self):
	
    def enqueue(self, x):
    # 데이터를 우선순위 맞춰서 저장함.
    
    def dequeue(self):
    
    def peek(self):

2. 트리(Trees)

1) 기본 정의

트리(Trees)는 2차원 자료 구조로, node와 edge를 이용하여 데이터의 배치 구조를 추상화한 자료 구조이다.

• root node: 최상단 node
• internal node: 중간 node들
• leaf node : 최하단 node(자식이 없는 node)
• parent node : 부모 노드
• child node : 자식 노드
• ancestor node : 조상 노드
• descendent node : 자손 노드
• 트리의 level : root(level 0), internal(level 1~n-1), leaf(level n).
• 트리의 높이(height)(깊이(depth)) : 최대 level + 1
• node의 차수(degree) : 해당 node의 subtree의 수(# of edges)

2) 이진 트리(Binary Trees)

모든 node의 degree가 2 이하인 트리이거나 empty 트리인 경우를 이진 트리(Binary Trees)라 부른다.

1. 포화 이진 트리(Full Binary Trees) : 모든 level에서 node들이 모두 채워져 있는 이진 트리. or 높이가 k인 트리에서 # of nodes가 2^k -1인 이진 트리.
2. 완전 이진 트리(Complete Binary Trees) : 높이가 k인 트리에서 k-2 level까지는 포화이진트리이며 k-1 level에서는 node들이 순서대로(왼쪽부터) 채워져 있는 이진 트리.

3. 이진 트리의 순회(Traversal of Binary Trees)

1) 깊이 우선 순회(Depth First Traversal)

1. 중위 순회(in-order traversal) : left-root-right 순서로 방문.
2. 전위 순회(pre-order traversal) : root-left-right 순서로 방문.
3. 후위 순회(post-order traversal) : left-right-root 순서로 방문.

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

    def size(self):
        # 현재 subtree의 포함된 node의 수를 return.
        # recursive한 방법으로 구현.
        # return left subtree size + 1 + right subtree size
        
    def depth(self):
        # 현재 subtree의 depth를 return
        # left subtree와 right subtree의 depth 중 더 큰 것 + 1를 return
        
    def inorder(self):
        # left-root-right 순서로 방문
        
    def preorder(self):
        # root-left-right 순서로 방문
        
    def postorder(self):
        # left-right-root 순서로 방문

class BinaryTree:
    def __init__(self, r):
        self.root = r # root node를 저장

    def size(self):
        
    def depth(self):
        
    def inorderTraversal(self):
        
    def preorderTraversal(self):
        
    def postorderTraversal(self):
    

2) 넓이 우선 순회(Breadth First Traversal)

1. level이 낮은 node들을 우선 방문한다.
2. level이 같은 node들에 대해서는, 부모 노드의 방문 순서에 따라 방문하며, 좌->우 순서로 방문한다.

이는 recursive한 방식으로 구현하기가 힘들다. 이를 만족하기 위해서 한 노드의 방문 후, 다음 노드들을 순서대로 기록해 두어야 한다. 따라서, 이를 위해 큐(Queue)를 활용한다.

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

    def size(self):
        # 현재 subtree의 포함된 node의 수를 return.
        # recursive한 방법으로 구현.
        # return left subtree size + 1 + right subtree size
        
    def depth(self):
        # 현재 subtree의 depth를 return
        # left subtree와 right subtree의 depth 중 더 큰 것 + 1를 return
        
    def inorder(self):
        # left-root-right 순서로 방문
        
    def preorder(self):
        # root-left-right 순서로 방문
        
    def postorder(self):
        # left-right-root 순서로 방문

class BinaryTree:
    def __init__(self, r):
        self.root = r # root node를 저장

    def size(self):
        
    def depth(self):
        
    def inorderTraversal(self):
        
    def preorderTraversal(self):
        
    def postorderTraversal(self):
    
    def bft(self):
    	# root노드가 존재한다면 queue에 root 노드를 enqueue한다.
        # queue가 빌 때까지 다음 과정들을 반복한다.
        # 1. queue에 들어 있는 노드를 dequeue한 후, 해당 노드를 방문. 
        # 2. 왼쪽 노드가 존재하면 왼쪽 노드를 queue에 enqueue한다.
        # 3. 오른쪽 노드가 존재하면 오른쪽 노드를 queue에 enqueue한다.

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

모든 노드에 대해서, key 값이 left subtree < current node < right subtree인 이진 트리이다.

이진 탐색 트리의 장단점은 다음과 같다.

• 장점) 데이터 원소의 추가, 삭제가 용이하다. 일반적으로 탐색에 걸리는 시간 복잡도가 O(log(n))으로 빠르다.
• 단점) 공간 소요가 크다. key 값이 1 -> 2 -> 3 -> 4 -> 5 .. 처럼 한쪽으로 치우친 이진 트리가 될 경우, 탐색에 걸리는 시간 복잡도가 O(n)으로 선형 탐색과 유사하다.

따라서, 이진 탐색 트리는 균형 잡힌 트리가 되는 것이 중요한데, 이를 위한 ANL 트리, Red-black 트리 등의 자료 구조가 있다.

이진 탐색 트리의 구성 요소)

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

    def inorder(self):

    def min(self):

    def max(self):

    def lookup(self, key, parent=None):

    def insert(self, key, data):

    def countChildren(self):

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

    def inorder(self):

    def min(self):
        # 최소 key값을 갖는 node를 return.

    def max(self):
        # 최대 key값을 갖는 node를 return.

    def lookup(self, key):
        # 해당 key값을 갖는 node와 부도 노드를 return.
        # 없으면 None return.

    def insert(self, key, data):

    def remove(self, key):
        # key를 이용해서 노드를 찾는다.
        # 삭제한 경우 True, 해당 키의 노드가 없는 경우 False

5. 힙 (Heaps)

1. MaxHeap : root의 key값이 최댓값이며, 모든 노드의 key값이 자식 노드의 key값보다 크거나 같은 완전 이진 트리.
2. MinHeap : root의 key값이 최솟값이며, 모든 노드의 key값이 자식 노드의 key값보다 작거나 같은 완전 이진 트리.

이진 탐색 트리(Binary Search Tree) vs. 힙(Heap)

비교	이진 탐색 트리	힙
원소들의 완전한 정렬	O	X, 느슨한 정렬
특정 key 값의 탐색 속도	빠름	느림
제약 조건	X	완전 이진 트리이어야 함
삽입, 삭제 속도		빠름, O(log(n))

완전 이진 트리의 노드들의 index 특징)

• 현재 노드 : m
• 부모 노드 : m // 2
• 왼쪽 자식 노드 : 2m
• 오른쪽 자식 노드 : 2m + 1

위 특징으로 인해, 배열로 구현하면 편리하다.

class MaxHeap:
    def __init__(self):
        self.data = [None] # 빈 maxheap 생성.

    def insert(self, item):
        # 맨 마지막에 해당 item을 추가한다.
        # 해당 데이터 원소를 부모 노드와 비교하며 최대 비교 회수: log_2(n)
        # 부모 노드보다 값이 크다면 switch한다.

    def remove(self):
        # 1. 루트 노드를 제거한다.
        # 2. 트리의 마지막 노드를 임시로 루트 노드에 배치한다.
        # 3. 자식 노드들과 비교하며 아래로 이동한다.
        # 3-1. 왼쪽과 오른쪽 자식 중 큰 값을 기준으로 switch한다.

    def maxHeapify(self, i):

Max/Min Heap의 응용)

1. 우선 순위 큐(Priority Queue) : 어차피 root node(최대 or 최소 key값)를 pop하면 되기에 우선 순위 큐에 유용하다.
2. 힙 정렬(Heap Sort) : 1)삽입(log_2(n)) -> 2)힙이 빌 때까지 하나씩 삭제(log_2(n)) 과정으로 유연하게 구현할 수 있다. 또한, 시간 복잡도도 O(nlog(n))으로 빠르다.