Week6

Priority Queue

---

우선순위 큐는 큐와 비슷한 자료구조이지만, 가장 먼저 들어온 데이터를 가장 앞에서 처리하는 것이 아닌 우선순위가 가장 높은 데이터를 앞에서 처리하는 자료구조입니다.

구조

---

• Binary tree
• 자신보다 낮은 곳에 위치한 곳엔 우선순위가 낮은 데이터가 저장되어 있음

데이터 삽입

---

• 가장 끝에 데이터를 추가 후 자신의 바로 위에 있는 데이터와 비교하며 반복적으로 위치를 변경

데이터 삭제

---

• 가장 마지막 위치에 있는 데이터와 우선 순위가 가장 높은 데이터를 바꾼 뒤, 맨 뒤의 데이터를 삭제
• 이후 맨 위의 데이터를 바로 아래 데이터와 비교하며 반복적으로 위치를 변경

주요 연산

---

• 우선 순위가 가장 높은 데이터를 가져옴: O(1)
• 데이터 추가 : O(log N)
• 우선 순위가 가장 높은 데이터를 삭제: O(log N)

+) 최솟값을 반환하기 위해서는?

---

• 우선 순위 큐에서 동작하는 부등호를 반대로 뒤집어야 한다!
• 즉 값을 (-)를 붙혀서 집어넣는다.(처리에 주의!)

Set(Binary Search Tree)

---

Set은 자신의 왼쪽 밑은 자신보다 작은 수, 오른쪽 밑은 자신보다 큰 수를 넣는 Binary tree구조의 자료구조입니다. 데이터의 추가/제거는 O(log N)의 시간 복잡도를 가집니다.

Line Sweep Algorithm

---

Line Sweep또는 Sweep algorithm이라고도 불리는 알고리즘입니다. 정렬된 데이터가 주어졌을 때, 데이터를 정렬된 순서대로 하나씩 처리하는 알고리즘입니다. 즉 데이터를 순차적으로 살펴보며 매 단계 어떤 작업을 해주면 최종적으로 원하는 답을 구할 수 있습니다.