자료구조21 [백준/C,C++] 1655번: 가운데를 말해요 www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 풀이 생각보다 꽤 어려웠던 문제입니다. 우선순위 큐 2개를 써서 해결할 수 있는 문제인데 핵심은 이렇습니다. 우선 내림차순의 우선순위 큐(pqMin)와 오름차순의 우선순위 큐(pqMax)를 준비합니다. pqMin에는 중간값보다 작은 값들을 담고, pqMax에는 중간값보다 큰 값들을 담습니다. 이때, pqMin을 pqMax의 사이즈와 같거나 1만큼 크게 유지하면, pqMin의 top()은 항상 가.. 2021. 4. 21. [백준/C,C++] 11286번: 절댓값 힙 www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 절댓값 힙을 구현하는 문제입니다. #include using namespace std; const int MAX = 100001; class AbsMinHeap { private: int heap[MAX]; int idx = 0; public: int size(); bool condition(int child, int parent); void push(int data); int pop.. 2021. 4. 21. [백준/C,C++] 1927번: 최소 힙 www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 최소 힙을 구현하는 문제입니다. #include using namespace std; const int MAX = 100001; class MinHeap { private: int heap[MAX]; int idx = 0; public: int size(); void push(int data); int pop(); void swap(int* a, int* b); int select(in.. 2021. 4. 21. [백준/C,C++] 11279번: 최대 힙 www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 풀이 최대 힙을 구현하는 문제입니다. #include using namespace std; const int MAX = 100001; class MaxHeap { private: int heap[MAX]; int idx = 0; public: int size(); void push(int data); int pop(); void swap(int* a, int* b); int select(in.. 2021. 4. 21. 이전 1 2 3 4 ··· 6 다음