DevCourse TIL Day3 Week2

김태준·2023년 4월 12일
0

Data Enginnering DevCourse

목록 보기
3/93
post-thumbnail

Day3 학습 내용 정리

어제 Day2 연결리스트, 스택에 이어 오늘 학습할 내용은 마찬가지로 자료구조인데 학습할 종류로는 queue, circular queue, heapq, 트리, 이진 트리 등이다!

✅ Queue

  • FIFO (선입선출 형태) 특징을 가지는 선형구조
  • enqueue 삽입과 dequeue가 존재
  • 자료 생성과 그 자료를 이용하는 작업이 비동기적으로 일어나는 경우
  • 자료 생성이나 자료 이용하는 작업이 여러 곳에서 일어나는 경우

🎈 큐의 추상적 자료구조 구현

  • array를 이용한 구현
    -> dequeue만 O(n)이고 나머지 함수는 O(1)
  • LinkedList를 이용한 구현
    -> dequeue 연산도 상수시간에 처리 가능!

파이썬 내장 Queue에 대해 살펴보면 다음과 같다.

from pythond.basic.queue import Queue
Q = Queue()
dir(Q)
# : __doc__, __init__, __module__, dequeue, enqueue, isEmpty, items, size 내부 메서드 존재

LinkedList로 구현한 큐는 다음과 같다. (이전 시간 학습한 DoublyLinkedList 활용)

# 링크드리스트 큐 생성
class LinkedListQueue:
    def __init__(self):
        self.data = DoublyLinkedList()
	# getLength로 노드 수 확인
    def size(self):
        return self.data.getLength()
    # size == 0으로 비어있나 여부 확인
    def isEmpty(self):
        return self.size() == 0
    # self.size+1 위치는 끝을 의미하므로 node 넣기
    def enqueue(self, item):
        node = Node(item)
        self.data.insertAt(self.size()+1, node)
    # popAt(1) 활용 (FIFO이므로)
    def dequeue(self):
        self.data.popAt(1)
    # getAt(1)로 1번에 위치한 데이터 찾기
    def peek(self):
        self.data.getAt(1).data
def solution(x):
    return 0

✅ Circular Queue

queue도 어쨌든 list라는 메모리를 사용하므로 길이가 길어지면 효율성이 떨어지는 문제가 발생한다. 이를 해결하고자 한 것이 환형 큐로, 정해진 개수의 저장 공간을 빙빙 돌며 탐색한다.

  • 데이터 넣는 포인트 : rear
  • 데이터 빼는 포인트 : front
  • ❗큐 길이를 저장하고 있는 것이 핵심

< enqueue, dequeue, peek 구현 >

    def enqueue(self, x):
    	# 꽉차있으면 에러 출력
        if self.isFull():
            raise IndexError('Queue full')
        # 데이터를 넣는 위치는 +1 하다가 범위를 벗어나면 다시 초기로 돌아가도록
        self.rear = (self.rear+1) % self.maxCount
        self.data[self.rear] = x
        self.count += 1

    def dequeue(self):
    	# 현 큐가 비었으면
        if self.isEmpty():
            raise IndexError('Queue empty')
        # 데이터를 빼는 위치는 +1 하다가 범위를 벗어나면 다시 초기로 돌아가도록
        self.front = (self.front+1) % self.maxCount
        # front에 위치한 data를 x에 저장하고 리턴
        x = self.data[self.front]
        self.count -= 1
        return x

    def peek(self):
        if self.isEmpty():
            raise IndexError('Queue empty')
        # dequeue함수에서 구현한 self.front를 그대로 사용해주어야 함
        return self.data[(self.front+1) % self.maxCount]

✅ Priority Queue

  • 우선순위에 따라 큐에서 원소들이 빠져나오는 방식 (Not FIFO)
  • ex) OS - CPU Scheduling

2가지 방식으로 구현 가능하다.

    1. enqueue 시 우선 순위 유지 -> 이미 정렬된 큐인 경우 훨씬 더 유리
    1. dequeue 시 우선 순위 높은 것 선택 - > O(n) 걸리게 됌

< enqueue 구현 >

    def enqueue(self, x):
    	# 들어갈 새 노드 정의 
        newNode = Node(x)
        # 현 큐의 head로 curr 지정
        curr = self.queue.head
        # 다음 위치가 tail이 아니고 다음 위치한 데이터가 더 커야지만 우선순위 큐에 삽입
        while curr.next != self.queue.tail and x < curr.next.data:
            curr = curr.next
        # curr 이후 노드에 삽입이므로 insertAfter 사용
        self.queue.insertAfter(curr, newNode)

🎇 queue 정리

기존에 사용하던 큐는 from collections import deque (BFS), import heapq로 모듈을 그대로 불러와 사용했었다.
이번 DevCourse를 진행하며 직접 class, 모듈을 거쳐 작동 방식에 대해 직접 구현해보는 시간을 가지며 좀 더 자료구조에 대한 이해도가 높아진 것 같다.✈️

✅ Tree

  • 컴퓨터 알고리즘 여러 곳에서 사용되고 있음 (검색에 용이)
  • node, edge를 이용해 데이터 배치 형태를 추상화한 자료 구조
  • 추가적인 정리 내용은 아래 링크에 있습니다.
    Tree

< 코드로 간단히 Tree를 size(노드 수), depth(길이 수)함수를 구현해보면 다음과 같다 >

class Node:
    def __init__(self, item):
        self.data = item
        self.left = None
        self.right = None
    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
    def depth(self):
        l_depth = self.left.depth() if self.left else 0
        r_depth = self.right.depth() if self.right else 0
        return max(l_depth, r_depth) + 1

class BinaryTree:
    def __init__(self, r):
        self.root = r
    # root가 있다면 재귀    
    def size(self):
        if self.root:
            return self.root.size()
        else:
            return 0
    # root가 있다면 재귀
    def depth(self):
        if self.root:
            return self.root.depth()
        else:
            return 0
def solution(x):
    return 0

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

  • 전위 순회(pre-order) : 노드 x 방문 후 왼쪽 서브트리 순회, 오른쪽 서브트리 순회
  • 중위 순회(in-order) : 왼쪽 서브트리 순회 후 노드 x 방문, 그리고 오른쪽 서브트리 순회
  • 후위 순회(post-order) : 왼쪽 서브트리 순회, 오른쪽 서브트리 순회, 노드 x 방문

코드로 구현해보면 다음과 같다.

class Node:
    def __init__(self, item):
        self.data = item
        self.left = None
        self.right = None
   	# 전위 순회 
	def preorder(self):
        traversal = []
        traversal.append(self.data)
        if self.left:
            traversal += self.left.preorder()
        if self.right:
            traversal += self.right.preorder()
        return traversal
    # 중위 순회
    def inorder(self):
        traversal = []
        if self.left:
            traversal += self.left.inorder()
        traversal.append(self.data)
        if self.right:
            traversal += self.right.inorder()
        return traversal
    # 후위 순회
	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 __init__(self, r):
        self.root = r
    # 전위 순회
    def preorder(self):
        if self.root:
            return self.root.preorder()
        else:
            return []
	# 중위 순회
    def inorder(self):
        if self.root:
            return self.root.inorder()
        else:
            return []
	# 후위 순회            
	def postorder(self):
        if self.root:
            return self.root.postorder()
        return []

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

  • 수준(level)이 낮은 노드를 우선 방문 
class BinaryTree:
    def __init__(self, r):
        self.root = r
    # 탐색 실시
    def bft(self):
    	# 빈 큐, 방문 노드 리스트 생성
        traversal = []
        queue = ArrayQueue()
        # 루트가 비어있지 않으면 queue에 루트 넣기
        if self.root:
            queue.enqueue(self.root)
        # 큐가 빌때까지 반복하는데, 왼쪽 , 오른쪽 순서로 탐색
        while not queue.isEmpty():
            x = queue.dequeue()
            traversal.append(x.data)
            if x.left:
                queue.enqueue(x.left)
            if x.right:
                queue.enqueue(x.right)
        return traversal

🎈 이진탐색트리 (Binary Search Tree)

모든 노드에 대해 왼쪽 서브트리는 현 노드보다 작고, 오른쪽 서브트리는 현 노드보다 큰 성질을 만족하는 이진 트리

  • 데이터 원소 추가, 삭제가 용이, 공간 소요가 크고 O(logN)의 공간복잡도를 갖는다.(항상은 아님)
  • 각 노드는 (key, value)를 가짐

구현방식에 앞서 삭제 과정이 조금 까다롭다.
총 3가지 경우로 나누어 볼 수 있다.

    1. 노드가 자식이 없는 경우, 삭제하려는 노드의 부모 노드를 찾아 해당 노드와의 연결을 끊고, 부모 노드가 root인 경우 None 처리
    1. 노드가 1개인 경우, 삭제한 노드의 자식을 부모노드와 연결시켜주면 되는데 대소 비교를 통해 왼쪽, 오른쪽 2개의 자식 중 연결을 골라서 해주어야 한다.
    1. 노드가 2개인 경우, 삭제하려는 노드의 오른쪽 서브트리 중 가장 작은 값으로 현 위치에 대체

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

def remove(self, key):
	# 해당 키를 가진 위치의 node, 부모노드 찾기
	node, parent = self.lookup(key)
    if node:
    	# 노드가 있다면 자식이 몇명인지 세기
    	nChildren = node.countChildren()
        # 1. 자식이 없는 경우
        if nChildren == 0:
        	# 부모가 있다면 삭제할 노드가 부모의 왼쪽, 오른쪽인지 확인 후 None 처리
            if parent:
            	if node == parent.left:
                	parent.left = None
                else:
                	parent.right = None
            # 부모가 없다면 (root)를 의미한다.
            else:
            	self.root = None
        # 자식이 1개인 경우 자식 위치가 왼쪽인지 오른쪽인지 확인 후 child로 지정
        elif nChildren == 1:
        	if node.left:
            	child = node.left
            else:
            	child = node.right
            # 부모 노드가 있다면, 왼쪽,오른쪽 위치 확인 후 child 처리
            if parent:
            	if node == parent.left:
                	parent.left = child
                else:
                	parent.right = child
            # 부모가 없다면 root를 child 처리
            else:
            	self.root = child
        # 자식이 2개인 경우 삭제할 노드의 오른쪽 서브트리 중 가장 왼쪽 값 찾기
        else:
        	# 부모 = 자식 처리, successor 자식 기준 오른쪽 서브트리
        	parent = node
            successor = parent.right
            # 오른쪽 서브트리의 제일 작은 값 따라가기 (해당 값으로 변환 필요)
            while successor.left:
            	# parent는 찾으려는 값의 부모, successor는 해당 값이 됌
            	parent = successor
                successor = successor.left
            node.key = successor.key
            node.data = successor.data
            # 찾으려는 값의 부모 노드 자식 중 왼쪽이냐, 오른쪽인가로 찾기 
            if parent.left == successor:
            	parent.left = successor.right
            else:
            	parent.right = successor.right

🎇 Tree 정리

기본 트리 구조(size, depth), 깊이 우선, 넓이 우선, BST 등을 직접 구현해보면서 알아보았다.
이전에 트리 자료구조에 대해 학습한 적이 있었지만, 이렇게까지 class로 직접 구현하면서 진행한 적은 없어 이번 기회에 자료구조에 대해 전반적으로 깊게 이해할 수 있는 시간이 되었다.
특히 BST의 경우 원소들이 전부 크기 순서대로 정렬되어 있어 inorder탐색으로 데이터를 순서대로 뽑을 수 있어 검색에 용이한 점을 다시 한번 정리하며 알게 되었다.💯

✅ Heap

최대 힙 : 루트가 최대값인 트리
최소 힙 : 루트가 최소 값인 트리
힙은 다음 3가지 성질을 따른다.

  • 루트 노드가 항상 (최댓값 or 최솟값)을 가진다.
  • 완전 이진 트리 -> 노드 수 n일때, 항상 logN의 시간에 비례, 추가 삭제는 마지막 노드에만 적용
  • 최대 힙 내 임의 노드를 루트로 하는 서브트리 역시 최대 힙 (최소 힙도 마찬가지)

코드로 최대 힙의 삽입과 삭제과정을 보면 다음과 같다

# MaxHeap
class MaxHeap:
    def __init__(self):
        self.data = [None]
	< 최대 힙에서의 삽입 >    
    def insert(self, item):
    	# 데이터 끝에 원소 추가
        self.data.append(item)
        # 끝 인덱스 idx로 저장
        idx = len(self.data) - 1
        # 루트보다 크고, 부모 노드와의 대소 비교로 자식이 더 크면 교환
        while idx > 1 and self.data[idx] > self.data[idx//2]:
            self.data[idx], self.data[idx//2] = self.data[idx//2], self.data[idx]
            idx //= 2
    < 최대 힙에서의 삭제 >
    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)
        else:
        	data = None
        return None
    # 최대 힙 되도록 정리
    def Heapify(self, i):
    	left = 2*i
        right = 2*i + 1
        smallest = i
        if left < len(self.data) and self.data[left] > self.data[smallest]:
        	smallest = left
        if right < len(self.data) and self.data[right] > self.data[smallest]:
        	smallest = right
        if smallest != i:
        	self.data[i], self.data[smallest] = self.data[smallest], self.data[i]
        	self.Heapify(smallest)
profile
김태준
To be a DataScientist
이전 포스트

DevCourse TIL Day2 Week2

다음 포스트

DevCourse Day3 Week2 Coding Test

0개의 댓글