우선순위 큐

문제 2014번: 소수의 곱 첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 541보다 작거나 www.acmicpc.net 풀이 수학, 우선순위 큐 [백준][C++] 2075: N번째 큰 수 문제 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmic kantatatam.tistory.com 위의 문제와 약간 비슷하다. 위의 문제는 전체 수 중에서 N번째로 큰 수를 찾는 문제로, ..

문제 1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net 풀이 그리디, 정렬, 우선순위 큐 ✔ 정답 코드 1 연료가 높은 주유소가 top에 위치하도록 우선순위 큐에 넣는다. 우선순위 큐를 top에서 부터 방문하며, top이 현재 방문할 수 없는 주유소라면 벡터에 넣는다. 현재 방문할 수 있는 주유소가 top에 위치하였을 때, P에 더하고 벡터에 있는 값들을 다시 우선순위 큐에 넣는다. 이를 P가 L 이상일 때까지 반복 이렇게 하면 다음 방문할 주유소를 탐색할 때, 우선순위 큐..

문제 2696번: 중앙값 구하기 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주 www.acmicpc.net 풀이 우선순위 큐 [백준][C++] 1655: 가운데를 말해요 문제 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 kantatatam.tistory.com 위의 문제와 풀이가 같다. 들어오는 수를 저장해 두고, 홀수번마다 현재 중앙값을 출력한다. 코드 #include #inc..

문제 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 풀이 그리디, 우선순위 큐 [백준][C++] 2109: 순회강연 문제 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불 kantatatam.tistory.com 위의 문제와 같지만 이 문제가 N이 더 크기때문에, 같은 풀이로는 시간 초과가 발생하였다. 각 날짜 별로 풀 수 있는 문제..

문제 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 풀이 그리디, 우선순위 큐 강연료를 최대로 받기 위해서는, 강연료가 크면서 기간이 많이 남은 강연은 최대한 나중에 하고, 기간이 짧은 강연을 빠른 날짜에 해야 한다. 우선순위 큐를 이용해서, 강연료가 크면서 남은 기간이 오래 남은 강연 순서로 탐색한다. 현재 탐색 중인 강연을 최대한 나중으로 미뤄서 실행하면 기간이 얼마 남지 않으면서 강연료가 큰 강연을 앞에 날짜에 실행할 수 있다. // 강연료가 크면서, 남은 기간이 오..

문제 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 풀이 방향 비순환 그래프, 위상 정렬, 우선순위 큐 방향 비순환 그래프, 위상 정렬, 우선순위 큐를 합친 문제이다. 기본적인 풀이 방법은 다음과 같다. B문제를 풀기 위해서는 A문제를 먼저 풀어야 한다. 입력으로 A, B가 들어오면 A의 outdegree로 B가 추가되고, B의 indegree가 1 증가한다. 문제는 쉬운 문제부터 풀어야 하므로, 우선순위 큐로 현재 풀 수 있는 문제 중에서 난이도가 가장 낮은 문제가 top에 ..

문제 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 풀이 우선순위 큐 참고: tantk land o-tantk.github.io [1655번] 가운데를 말해요 문제 출처 : https://www.acmicpc.net/problem/1655 알고리즘 분석 : 문제 해결에 필요한 사항1. 최대 힙, 최소 힙2. Priority Queue3. pq로 중간 값 구하는 방식 중간값 구하기 알고리즘은 다음과 같다. 1. 최대 힙 www.crocus.co.kr 수열에서 중앙값을 찾는 것은 쉽지만, 데이터..

문제 19598번: 최소 회의실 개수 2개 회의실로 3개 회의를 모두 진행할 수 있다. 예를 들어, 첫번째 회의실에서 첫번째 회의를 진행하고 두번째 회의실에서 두번째 회의와 세번째 회의를 진행하면 된다. 1개 회의실로 3개 회의 www.acmicpc.net 풀이 그리디, 우선순위 큐 [백준][C++] 11000: 강의실 배정 문제 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 풀이 그리디, 우선순위 큐 [백준][C++] 2170: 선 긋기 문제 풀 kantatatam.tistory.com 위의 문제와 풀이가 같은 문제 코드 #include #include ..

문제 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 풀이 그리디, 우선순위 큐 가장 작은 수를 만들기 위해서는 뽑는 카드가 현재 상태에서 가장 작은 2장의 카드를 뽑아야 한다(그리디). 현재 상태에서 가장 작은 카드를 뽑기 위해 우선순위 큐를 사용한다. 우선순위 큐의 탑에 있는 카드를 2장 뽑는다. 2장의 카드를 더한 값을 우선순위 큐에 2번 더한다. 이를 m번 반복한다. 여기서 카드의 수가 크기때문에 자료형은 long long을 사용해야 한다. 코드 #include #i..

문제 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 풀이 우선 순위 큐 모든 수를 vector에 넣으면 메모리 초과가 발생한다. 수를 입력받으면서 바로 처리해줘야 한다. 오름차순 우선순위 큐를 만든다. 우선순위 큐는 입력받으면 바로 정렬되므로 top에는 큐에서 가장 낮은 값이 위치하게 된다. 즉, 우선순위 큐의 size를 N으로 제한한 상태에서 i번째 수까지 입력받으면, top에는 i번째 수 중에서 N번째로 큰 수가 위치하게 된다. 코드 #include #include using namespace std; prio..