tose33

https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 그냥 max heap 우선순위 큐를 쓰면 되는 문제 였다. 직접 우선순위 큐를 구현해볼까 생각했는데 그냥 .. 귀찮아서 스킵 ..

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 이 문제는 시간제한이 0.1초이고 주어지는 숫자의 최대 갯수가 10만개다. N회 동안 가운데 숫자를 계속 찾아야 한다. 어쨌든 숫자가 추가 될때마다 추가 하고 정렬이 필요하기 때문에 우선순위 큐를 생각해볼수 있는데 문제는 시간제한이 0.1초고 N의 최대 갯수가 10만개다. 10만회 동안 우선순위 큐에 요소를 추가하면, 요소를 pq에 추가할때마다 log(pq.size())가 소요 되..

https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 쉽지 않은 문제였는데, 이해하고 나면 원리는 간단하다. pair형을 담는 pair.second 기준 min heap 우선순위 큐를 이용한다. (즉 컵라면 기준 min heap) 우선 주어지는 문제들을 데드라인 기준 오름차순 정렬해서 데드라인이 작은 문제부터 탐색한다. 데드라인이 현재 일수 보다 크거나 같으면 우선 우선순위 큐에 담고 일수를 1 늘린다. 이렇게 일들을 우선순위 큐에 담다가 데드라인이 현재 일..

https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 우선순위 큐 구조체만 잘 구현해주면 되는 문제였다. https://tose33.tistory.com/456 c++) priority_queue cmp 구조체 정의 https://en.cppreference.com/w/cpp/container/priority_queue std::priority_queue - cppreference.com template< class T, class Container = std::vector , class Comp..