https://www.acmicpc.net/problem/2696 2696번: 중앙값 구하기 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주 www.acmicpc.net 우선순위 큐를 2개 이용하는 문제로 왼쪽은 최대힙, 오른쪽은 최소힙으로 구현하여 중앙값을 구했다. 양쪽 힙의 len이 같을때는 왼쪽에 heappush를 하고 나머지는 오른쪽에 넣어준다. 이때 왼쪽의 최댓값이 오른쪽의 최솟값보다 크면 둘의 위치를 바꿔준다. 위의 과정을 반복하므로써 중앙값을 우선순위 큐를 이용하여 구할 수 있다. 손으로 예시를 들어서 직접 써보면 이해하기..

https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 사람마다 느끼는 난이도는 다르겠지만, 나한텐 개어려웠다. 처음에 min_heap과 max_heap을 다 만들어놓고 한쪽에서 삭제된걸 어떻게 삭제할까 하다가 그냥 remove()써서 삭제했더니 당연히 시간초과... 이 remove함수를 대체하여 다른것을 생각해내는데 시간이 매우 오래결렸다. (2틀동안 이것만 붙잡고 있었음) max_heap을 구현하는데 (-num,num) 의 튜플형태로 구현하여 ..

https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 이 문제는 파이썬의 우선순위 큐 자료구조가 무엇인지 안다면 어렵지 않게 해결할 수 있다. 파이썬에서는 우선순위 큐 자료구를 heapq모듈을 이용하여 사용할 수 있다. 스택: 가장 나중에 삽입된 데이터가 가장 먼저 나옴 큐: 가장 먼저 삽입된 데이터가 가장 먼저 나옴 우선순위 큐: 우선순위가 가장 높은 데이터가 가장 먼저 나옴 힙: 완전 이진트리의 일종으로 항상 루트 노드를 제..