priority_queue (2) 썸네일형 리스트형 [BOJ 7662, 어려움] 이중 우선순위 큐 (C++) 개인적인 난이도 어려움 생각대로 안돼서 개고생함 이게 왜 골드 4인지 모르겠다 알다시피 priority_queue는 heap으로 구현되어 있고 출력이 최상위 루트를 통해 이루어짐 heapify() 1번의 시간복잡도는 log(N). 입출력시 heapify가 이루어짐 이 문제의 제목을 통해 우선순위 큐 2개를 이용해 푸는 것이라고 짐작할 수 있음 최댓값, 최솟값을 출력해야 하므로, max heap 1개와 min heap 1개를 쓰면 된다고 짐작할 수 있음 그렇다면 입력은 2개의 힙 모두에 이루어질 것이고 출력은 둘 중 하나의 힙에서만 이루어질 것이다~ 그렇다면 두 힙의 동기화가 이 문제의 관건일 것이다~ 라고 짐작할 수 있음 실패한 풀이) insert연산 수행 횟수와 delete연산 수행 횟수가 같아질 때,.. [BOJ 1655, 쉬움] 가운데를 말해요 (C++) 개인적인 난이도 쉬움 똥싸면서 생각한대로 구현하니까 풀림 이게 왜 골드 2인지 모르겠다 https://www.acmicpc.net/problem/7662 얘는 비슷한 문제 같은데 아직 못 풀었다 얘는 골드 4임 실패한 풀이) set을 이용해서 구현하면 중간값을 쉽게 찾을 수 있다고 생각했다 안되는 이유 set은 일단 중복된 값을 처리하지 못한다. s.begin()부터 중간값까지 한칸씩 가는 시간이 오래 걸린다. N/2칸 이동을 총 N번 하니까 O(log n^2)임. (이진트리의 이분탐색의 장점을 살리지 못함) set은 red-black tree. 정렬이 자동으로 되는 균형 잡힌 이진트리임 탐색 시간 O(log n) 삽입/삭제 시간 O(log n) 실패 코드 #include #define fastio ci.. 이전 1 다음
