99클럽 코테 스터디 31일차 TIL + 우선순위 큐(PriorityQueue)(1)

학습 키워드

- 우선순위 큐(PriorityQueue)

 

공부한 내용

우선순위 큐(PriorityQueue)

• 큐 자료구조는 선입선출(FIFO) 방식이다.
• 우선순위 큐는 들어간 순서와 상관없이 높은 우선순위를 가진 원소가 먼저 나온다는 특징을 가진다.
• Heap을 이용하여 구현하는 것이 일반적이다.
• 데이터 추출 시, 루트 노드를 얻어 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입 후 아래 노드로 내려가면서 정렬하는 방식으로 진행된다.
• 숫자가 작을수록 먼저 나오는 큐를 최소힙(Min Heap)이라 하고,
• 숫자가 클수록 먼저 나오는 큐를 최대힙(Max Heap)이라고 한다.

우선순위 큐(Heap) 특징 및 시간 복잡도

특징

• 높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조이다.
• → 우선순위 큐에 들어가는 원소는 비교가 가능한 기준이 있어야 한다.
• 완전 이진트리 구조의 형태를 갖는다.
• 일반적으로 배열로 구현한다.
• 일종의 반 정렬 상태를 유지한다.(느슨한 정렬 상태)
• 우선순위를 중요시해야 하는 상황에 사용

우선순위 큐는 배열에 저장하되 삽입/ 추출 시 기존 정렬 상태를 유지하기에 O(logn)의 시간복잡도를 유지한다.

우선순위 큐의 특징

• 높은 우선순위의 요소를 먼저 꺼내서 처리하는 구조이다.(큐에 들어가는 원소는 비교가 가능한 기준이 있어야함)
• 내부 요소는 힙으로 구성되어 이진트리 구조로 이루어져 있다.
• 내부구조가 힙으로 구성되어 있기에 시간 복잡도는 O(NLogN)이다.
• 일반적으로 배열로 구현한다.
• 일종의 반 정렬 상태를 유지한다. (느슨한 정렬 상태이다.)

 

회고

발생한 문제

- 자료구조 공부가 부족하다는 생각이 들었다.

 

해결 방법

- 우선순위 큐에 대해 공부했다. 

 

 

 

참고 자료

- https://cobi-98.tistory.com/45

- https://coding-factory.tistory.com/603