어서와! 자료구조와 알고리즘은 처음이지? 정리 (2)

프로그래머스의 어서와! 자료구조와 알고리즘은 처음이지? 11-23강을 정리한 글입니다.

---

11-13강: 스택, 수식의 후위 표기법

• 스택: 원소를 한 쪽에서 밀어넣고, 같은 쪽에서 뽑아야 하는 자료구조
• infix → postfix 변환하기

14-16강: 큐, 환형 큐, 우선순위 큐

• 큐: 원소를 한 쪽에서 밀어 넣고, 다른 쪽에서 뽑는 자료구조

• 환형 큐

  • 기본 구현

    class CircularQueue: 
        def __init(self,n): 
          self.maxCount = n 
          self.data = [None]*n 
          self.count = 0 
          self.front = -1 
          self.rear = -1

• 우선순위 큐: 우선순위에 따라 원소들이 꺼내지는 큐

17-19강: 트리, DFS, BFS

• 트리: node와 edge를 통해 데이터를 배치
• 이진 트리: 모든 노드의 차수가 2 이하인 트리
  • 재귀적으로 구현

기본 구현

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

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

DFS

• 한 정점에서 인접한 모든 정점을 다 방문하되, 각 정점에서 DFS를 끝낸 뒤 이동한다.

class Node:
  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 []

BFS

• 한 정점에서 인접한 모든 정점을 방문하되, 각 정점에서 인접한 모든 정점을 방문하고 이동한다.

def bft(self):
    q = ArrayQueue()
    traversal = []
    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

20-21강: 이진 탐색 트리

• 모든 노드에 대해
  • 왼쪽 서브트리에 있는 데이터는 현재 노드의 값보다 작고,
  • 오른쪽 서브트리에 있는 데이터는 현재 노드의 값보다 크다.
• 데이터를 찾기에 용이하다.

기본 구현

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

• 노드를 삭제하는 경우 이진 탐색 트리의 구조를 유지하기 위해 조정이 필요하다.

  1. 말단 노드인 경우: 노드를 없애고, 부모 노드의 링크를 None으로 대입

  2. 자식이 하나 있는 경우: 삭제되는 노드 자리에 자식을 대신 배치, 부모노드의 링크 조정

  3. 자식을 둘 다 가지고 있는 경우: 삭제되는 노드보다 바로 다음 노드, Successor node를 찾는다.

     • S노드가 right child를 갖고 있는 경우: 그 노드를 삭제되는 노드 자리에 배치, S노드의 부모 노드의 left child로 이동

     • S노드가 자식 노드가 없을 경우: S 노드를 삭제되는 노드 자리에 놓고, 부모노드(=삭제하는 노드)의 오른쪽 link만 조정

• 트리가 한 쪽으로 치우쳐져 있는 경우에 비효율적이다.

22-23강: 힙

• 완전 이진 트리이고, 루트 노드가 언제나 최댓값 또는 최솟값을 가진다.
• 우선순위 큐, 힙 정렬 등에 쓰인다.