우선순위 큐
[C++] 라운드 로빈 스케줄링 구현 (우선순위 큐 이용)
EHProcess.h #pragma once #include #include using namespace std; class EHProcess { string pname; //프로그램 이름 const int tjob; //전체 작업량 const int cjob; //cpu 점유 시 수행가능 최대 작업량 int ntjob = 0; //현재 남은 작업량 int ncjob = 0; //현재 cpu 점유 시 수행가능 최대 작업량 public: EHProcess(string pname, int tjob, int cjob); //Idle 상태에서 Ready 상태로 전이 void IdleToReady(); //CPU를 점유하여 실행, 남은 작업량 반환 int Running(); //프로세스 종료 void EndPro..
[C#] 우선순위 큐 개념과 힙을 통한 구현
우선순위 큐란? 큐(Qeueu)는 FIFO(First In First Out) 방식을 따르기 때문에, 입력 순서대로 출력되는 데이터 구조인 반면, 우선순위 큐(Priority Qeueu)는 입력 순서와는 무관하게 우선순위대로 출력되는 데이터 구조다. 시간 복잡도 우선 순위 큐는 Enqueue()시, 내부적으로 정렬을 해주거나 또는 탐색을 해주어야하는 로직이 필요하다. 우선 순위대로 정렬하거나 탐색하는 방법으로 얼마나 효율적으로 만드느냐가 주제의 핵심 포인트다. 이 글에서는 'O(N)'과 'O(logN)' 두 가지 방식을 다룬다. 우선순위 큐 구현 방법과 종류 이진 탐색'O(logN)'과 단순 선형 탐색 차이'O(N)' Queue의 Enqueue()시, 내부적으로 효율적인 탐색 방법이 필요하다. 간단한 구..
[골4] 1715 - 카드 정렬하기
#include #include #include #pragma region 입출력 속도향상 #define FAST_IO() \ {\ ios::sync_with_stdio(false);\ cin.tie(NULL); \ cout.tie(NULL); \ }\ #pragma endregion using namespace std; int main() { FAST_IO(); int n, ans = 0; cin >> n; priority_queue pq; if (n == 1) { cout tmp; pq.push(tmp); } while (!pq.empty()) { int sum = 0; sum += pq.top(); pq.pop(); if (!pq.empty()) { sum += pq.top(); pq.pop(); ..
[골5] 13549 - 숨바꼭질 3
#include #include #include #include #include using namespace std; using IntPair = pair; #define MAX 100001 bool vis[MAX]; int MinSec(int n, int k) { priority_queue q; // 경과 시간을 기준으로 우선순위 큐 (짧을수록 우선순위 크다) q.push({ 0, n }); vis[n] = true; while (!q.empty()) { auto top = q.top(); q.pop(); int curSec = top.first, curLoc = top.second; // 목적지 도달 if (curLoc == k) return curS..
컨테이너 어댑터 (스택, 큐, 우선순위 큐)
컨테이너 어댑터(container adapter)란 기존 컨테이너의 인터페이스를 제한하여 만든 기능이 제한되거나 변형된 컨테이너를 의미한다. 이러한 컨테이너 어댑터는 각각의 기초가 되는 클래스의 인터페이스를 제한하여, 특정 형태의 동작만을 수행하도록 한다. 단, 반복자를 지원하지 않으므로 STL 알고리즘에서는 사용할 수 없다. 컨테이너 어댑터의 종류 STL에서는 컨테이너 어댑터로 다음과 같은 클래스 템플릿을 제공한다. stack queue priority_queue 스택(stack) 스택(stack) 컨테이너는 vector 클래스의 인터페이스를 제한하여, 전형적인 스택 메모리 구조의 인터페이스를 제공한다. 스택 컨테이너는 stack 헤더 파일에 정의되어 있다. 스택 메모리 구조는 선형 메모리 공간에 데이..