728x90 반응형 C++2 자료구조 - 우선 순위 큐(Priority Queue) 1. 우선순위 큐란? 우선순위 큐(Priority Queue)는 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리되는 자료구조이다. 큐는 선형 자료구조이고, 우선순위 큐는 비 선형 자료구조이다. 우선순위 큐는 자료가 들어온 순서와 상관 없이 미리 정한 우선순위대로 나간다. 주로 정의된 우선 순위를 heap condition으로 가지는 heap을 이용해 구현된다. 그 이유는 시간 복잡도와 관련이 있는데, 배열 기반 데이터 삽입의 시간 복잡도는 O(n) 이고 배열 기반 데이터 삭제의 시간 복잡도는 O(1)이다. 또 연결 리스트 기반 데이터 삽입과 삭제의 시간 복잡도도 위와 같다. 하지만 힙 기반 데이터 삽입과 삭제의 시간 복잡도는 각각 O(logn)이다. 따라서 힙을 먼저 공부해야 한다... 2021. 1. 7. 자료구조 - 큐 (Queue) 1. 큐란? 큐(Queue)는 데이터를 일시적으로 쌓아두기 위한 자료구조로, 먼저 들어온 데이터가 가장 먼저 나가는 First In First Out인 구조를 말한다. 위 Reference Code처럼 배열로 큐를 구현해도 되지만, 표준 라이브러리에 정의되어 있기 때문에 include하여 사용하면 편리하다. enqueue란 큐 맨 뒤에 데이터를 추가하는 것을 의미하며 dequeue란 큐 맨 앞쪽의 데이터를 삭제하는 것을 의미한다. 데이터가 삽입되는 곳을 front, 제거되는 곳을 back이라고 한다. 선언 queue 큐 이름; 형태로 선언한다. #include queue s1; queue s2; queue s3; 기본 메소드 1. push() : 큐 맨 뒤에 데이터 추가 = enequeue 2. pop(.. 2021. 1. 6. 이전 1 다음 728x90 반응형