우선순위큐3 [자료구조] 힙과 우선순위 큐(heap&priority queue) 이번 포스트에서는 힙과 우선순위 큐에 대하여 알아본다. 에서 많은 부분을 참고하여 정리했다. 우선순위 큐란 무엇일까? 우선 큐는 선입선출의 원칙에 의하여 먼저 들어온 데이터가 먼저 나가는 자료구조라는 사실은 알고 있다. 그렇지만 세상에는 우선순위에 따라 순서를 변경해야 하는 문제들이 있다. 소프트웨어를 예로 들어보자. 내가 핸드폰으로 1시간짜리 플레이리스트를 듣고 있었는데, 도중에 친구에게 전화가 온다. 이때 음악이 끝나지 않았다고 해서 단순하게 순서대로 일을 처리한다면 우리는 전화를 받지 못할 것이다. 따라서 각각의 프로세스에 우선순위를 부여하여 더 중요한 프로세스가 먼저 처리되도록 해야 한다. 이때 우선순위 큐를 사용하는 것이다. 우선순위 큐를 구현하는 방법으로는 배열을 이용하거나 연결리스트를 사용하.. 2022. 9. 21. [C++] STL을 이용한 우선순위 큐(priority queue) 저번 포스팅에서는 우선순위 큐와 힙에 대한 내용을 정리해 보았다. 그런데 우선순위 큐를 사용하기 위해서는 코드를 일일이 구현해야 하는 걸까? 그렇지 않다. C++에서는 STL(표준 C++ 라이브러리 Standard Template Library) 을 통해 프로그램에 필요한 자료구조와 알고리즘을 템플릿으로 제공하고 있다. 오늘은 이 STL을 이용한 우선순위 큐에 대해 알아본다. 이에 앞서 STL은 제네릭 알고리즘과 C++을 위한 데이터 구조체들의 첫 번째 라이브러리로서 만들어졌다는 사실을 짚고 넘어가면 좋을 것 같다. priority queue는 기본적으로 아래와 같은 문법으로 선언한다. #include priority_queue queue; 첫 번째 인자는 타입을 지정한다. 두 번째 인자는 컨테이너를 지.. 2022. 9. 18. [C++] 백준 1966 프린터 큐 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 문제 요약 FIFO - First In First Out 구조로 우선순위에 따라 문서를 인쇄하는 프린터기가 있다. 조건은 다음과 같다. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다. 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다. 문제: Queue에 있는 문서의 수와 중요도가 주어졌을 때, 어떤 한 문서가 몇 번째로 인쇄되는지 알.. 2022. 9. 18. 이전 1 다음
