야생가오리

https://www.acmicpc.net/problem/1655 부른 수들 중에서 중간값을 찾아내야 한다. 짝수개면 둘 중 더 작은거무작위로 부른 수들의 정렬이 필요하니 우선순위 큐를 사용해야 함을  생각할 수 있다. 예시인 1, 5, 2, 10, -99, 7, 5 을 생각해보면크기순 정렬하면 -99, 1, 2, 5, 5, 7, 10이 되고 중간은 5가 된다.이걸 왼쪽(작은값들)과 오른쪽(큰값들)으로 나눠서 생각해보자. 이러는 이유는 우선순위큐에서 우리가 쓸 수 있는 값은 어쨌든 top값밖에 없기 때문이다. 중간에 든 걸 뺄 수가 없는 구조니까 우린 중간값이 top에 오도록 만들어주는 편이 좋다.그렇다면 왼쪽(작은값들)은 내림차순(최대히프)으로,오른쪽(큰값들)은 오름차순(최소히프)으로 정렬해준다면, 각..

https://www.acmicpc.net/problem/7662 시간제한 6초여서 어떻게 문제 시간제한이 6초? 했는데 6번의 시도 6번의 시간초과로 얕본 업보를 받음문제자체는 단순하다... 수를 입력받고 명령에 따라 최댓값이나 최솟값을 삭제하기. 1트로는 그냥 깡 배열에 저장하고 최대냐 최소냐 입력받는 것에 따라 매번 sort를 통해 재정렬 후 삭제했다. 당연하지만 시간초과다. 쓰면서도 안 될 것 같았다그럼 제목에도 나와있듯 우선순위 큐를 쓰긴 써야 할 것 같은데, top이 최소냐 최대냐는 최소히프냐 최대히프냐에 따라 달라지므로 우선순위 큐 두 개가 필요하다.두개를 만들어서 저장해서 쓴다고는 치자. 문제는 두 큐를 동기화시키는 것이다. 최솟값 빼래서 최소히프에서 뺐는데 최대히프에서는 안 빼면 나중에 ..

https://www.acmicpc.net/problem/11279 최소힙 문제에서 우선순위 조건만 바꾸면 됨..날먹솔브드 클래스 필수문제에 둘다 있는걸 어케~#include #include #include using namespace std;priority_queue, less> pq;int solution(int x){ int answer; if(x==0){ if(pq.empty()) answer = 0; else { answer = pq.top(); pq.pop(); } } else { pq.push(x); } return answer;}int main(){ ios_..

https://www.acmicpc.net/problem/1927 걍 우선순위 큐 쓰는 문제...이왜 실2?씨쁠쁠은 짱이다 #include #include #include using namespace std;priority_queue, greater> pq;int solution(int x){ int answer; if(x==0){ if(pq.empty()) answer = 0; else { answer = pq.top(); pq.pop(); } } else { pq.push(x); } return answer;}int main(){ ios_base::sync_with_s..