[알고리즘] 11. 심화 자료구조

Index

1. 우선순위 큐와 힙

2. 트리

3. 바이너리 인덱스 트리

4. 참고자료

---

1.  우선 순위 큐와 힙

우선순위 큐

- 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조

- 데이터를 우선 순위에 따라 처리하고 싶을 때 사용

- 삽입/삭제시 O(logN)

- heap 정렬은 O(NlogN)

 

구현 종류

1) 리스트 이용해 구현

2) heap을 이용해 구현

 

Heap

- 완전 이진 트리 자료구조: root 노드부터 시작하여 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 삽입되는 tree

- Heap에서는 항상 root 노드를 제거

- Min Heap / Max Heap

Min-Heapify

원소 삽입

원소 삭제

 

힙 정렬

def heap_sort(iterable):
  h = []
  result = []
  for val in iterable:
    heapq.heappush(h, val)
  for i in range(len(h)):
    result.append(heapq.heappop(h))
  return result

 

2.  트리

트리(Tree)

 

이진 탐색 트리(Binary Search Tree) 

- 이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조

- 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

- 데이터 조회 과정: 해당 노드보다 작으면 왼쪽 자식 노드로, 크면 오른쪽 자식 노드로 이동, 같을 경우 완료

 

트리의 순회(Tree Traversal)

- pre-order traverse(전위 순회) : 루트를 먼저 방문

- in-order traverse(중위 순회): 왼쪽 자식을 방문한 뒤에 루트를 방문

- in-order traversse(후위 순회): 오른쪽 자식을 방문한 뒤에 루트를 방문

 

(트리 순회 구현)

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

# 전위 순회
def pre_order(node):
  print(node.data, end = ' ')
  if node.left != None:
    pre_order(tree[node.left])
  if node.right != None:
    pre_order(tree[node.right])
    
# 중위 순회
def in_order(node):
  if node.left != None:
    pre_order(tree[node.left])
  print(node.data, end = ' ')
  if node.right != None:
    pre_order(tree[node.right])

# 후위 순회
def post_order(node):
  if node.left != None:
    pre_order(tree[node.left])
  if node.right != None:
    pre_order(tree[node.right])
  print(node.data, end = ' ')
  
 n = int(input())
 tree = {}
 
 for i in range(n):
  data, left, right = input().split()
  if left == "None":
    left = None
  if right == "None":
    right = None
  tree[data] = Node(data, left, right)

pre_order(tree['A'])
print()
in_order(tree['A'])
print()
post_order(tree['A']

 

 

3.  바이너리 인덱스 트리

Binary Indexed Tree(=BIT)

- 2진법 인덱스 구조를 활용해 구간 합 문제를 효과적으로 해결해 줄  수 있는 자료구조(=fenwick tree)

- 0이 아닌 마지막 비트를 찾는 법: K & -K

 

 

- 구간 합 구하기(https://www.acmicpc.net/problem/2042)

 

---

참고 자료

[Video: 동빈나의 이코테 2021(우선순위 큐와 힙)] https://www.youtube.com/watch?v=AjFlp951nz0&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=12

[Video: 동빈나의 이코테 2021(트리)] https://www.youtube.com/watch?v=i5yHkP1jQmo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=12

[Video: 동빈나의 이코테 2021(바이너리 인덱스 트리)] https://www.youtube.com/watch?v=fg2iGP4e2mc&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=14