목록우선 순위 큐 (3)

Doby's Lab

[자료구조] 백준 7662번: 이중 우선순위 큐 (C++), 두 큐를 하나처럼, 싱크의 핵심

입력값을 넣을 때마다 즉각적으로 정렬을 시키면 되는 문제가 아닐까를 생각했지만 정렬의 시간 복잡도 O(NlogN), 연산의 최대 개수가 1,000,000이므로 이는 시간 초과를 발생시킨다. 즉, 이번 문제에서는 우선순위 큐(priority queue)의 사용을 유도한다. 큐의 특성상 pop(D)를 할 때는 앞에서 밖에 할 수 없기 때문에 두 개의 우선순위 큐를 선언해주었다. 오름차순과 내림차순. 두 개의 큐를 선언하여 풀었던 코드는 다음과 같다. #include #include #include #include #define ll long long using namespace std; int main() { int T; cin >> T; for (int i = 0; i < T; i++) { int n; c..
PS/BOJ 2021. 10. 21. 12:21
[자료구조] 백준 11279번: 최대 힙 (C++), 우선 순위 큐 사용

[틀렸던 코드] #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; vector arr; vector answer; for (int i = 0; i > idx; if (idx == 0) { sort(arr.begin(), arr.end()); if (!arr.empty()) { answer.push_back(arr.back()); arr.pop_back(); } else { answer.push_back(0); } } else { arr.push_back(idx); } } for (in..
PS/BOJ 2021. 10. 7. 08:23
[자료구조] 우선순위 큐 (Priority Queue) 개념, C++ STL

우선순위 큐란 큐의 한 종류로 말 그대로 우선순위대로 큐에 데이터를 집어넣는다. (여기서 말하는 우선순위란 값의 크기의 오름차순 혹은 내림차순 등 사용자가 정할 수 있다.) 일반적인 큐는 배열같은 선형적인 구조로 생각할 수 있다. 하지만, 우선순위 큐는 트리의 관점에서 접근해야 한다. 우선순위 큐는 배열 혹은 연결 리스트로도 구현이 가능하지만 이를 사용하지 않는 이유가 있다. 데이터를 삽입하거나 삭제하는 과정에서 배열이나 연결 리스트의 메모리를 밀고 당기는데에서 성능 저하를 일으키기 때문에 일반적으로 힙을 사용하여 구현하기 때문이다. (힙이 트리로 이루어졌기 때문) 그리고, 힙에서 데이터를 삽입하거나 삭제할 때는 시간 복잡도가 O(log N)이다. (+ 힙 정렬이 N개의 데이터를 하나씩 다 빼오기(삭제)..
C++ 2021. 10. 7. 08:03
이전 Prev 1 Next 다음