Algorithm/우선순위큐

백준 11000 강의실배정 c++ // 강의실배정 vs 회의실배정, pq cmp 구현시 주의점

https://www.acmicpc.net/problem/110001. 강의실배정 vs 회의실배정1. 회의실배정 : 시작시간이 빠른것부터 배정하면 된다. 배정이가능하다면, ret++ 하면된다.end변수를 사용한다 // 가장최근에 끝난 회의의 종료시간int end = 0; int tot = 0; while(pq.size() > 0){ sub = pq.top(); if(end 2. 강의실배정 :  시작시간기준으로정렬, pq는 종료시간기준으로 정렬top.sec과 입력값.first를 비교하며 가능하다면(즉, 같은 회의실 사용으로 처리하는것이다. -> pq.size가 써야되는 강의실의 수가 된다. 2. pq cmp 구현시 주의점1. cmp는 매개변수가 같으면 거짓을 리턴해야함2..

프로그래머스 이중우선순위큐 c++ // pq, multiset 사용법

https://school.programmers.co.kr/learn/courses/30/lessons/42628 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 우선순위큐 의사코드 1. 문제점 : 큐2개를두면, 실제 최대힙에서는 삭제되어도 최소힙에서는 삭제가 안되므로 제대로 비었는지 확인이 안된다 -> 해결 : cnt 변수 정의 //현재 큐에 있는원소의 갯수 2. 시키는대로 연산 구현후, cnt==0이면 실제로 pq1, pq2의 원소를 다 뺴주어야한다! (tc1번 걸림) 2. 우선순위큐 전체코드 #include using namespace std; ..

백준 1781 컵라면 c++ // 우선순위큐 정렬방법, 선택x인경우 처리방법

https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 1. 우선순위큐 정렬방법 매개변수가 같으면 false를 리턴해야함에 주의하자. class cmp { public: bool operator () (pair p1, pair p2) { if (p1.first == p2.first) { return p1.second p2.first; } }; 2. 문제점 기한순 정렬후 최대컵라면 뽑는방법 -> 기한을 ..

백준 1655 가운데를말해요 c++ // 우선순위큐 2개로 정렬효과만들기

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 1.시간복잡도 정렬후 mid 인덱스 출력 - > N ( 10만) * NlgN(정렬) -> 시초 특정알고리즘 필요 : pq, dp, 이분탐색 등.. 정렬한효과 -> pq 2개로 구현 2. 의사코드 maxHeap의 top이 항상 중간값이 되도록 고정하면 자동정렬이 된다. 이럴려먼 maxHeap의 크기가 minHeap의 크기보다 같거나 1이 커야한다. 1. 입력온값을 어디에 넣을것인가?..

백준 2075 n번째큰수 c++ // 우선순위큐, 발상, 수학

https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 1.의사코드 1. 작은것부터 넣기 2. 메모리제한 -> 큐에n개이상이면 pop 하기 3. top에 있는애가 n번째 큰수임 ex) 1~7에서 5번째 큰수는 3이다. pq에 6이 올때, 5(n) top(1제거) pq에 7이 올때, 5(n) top제거(2제거) 이후 top 에있는 놈이 정답인 3이다. 2. 전체코드 ios sync 코드를 빠뜨렸더니 시간초과가 났다.. #include using namespac..

백준 1715 카드정렬하기 c++ // 우선순위큐, 그리디, 허프만코드

https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 1. 의사코드 1. 최소값을 2개씩더하고, q에넣기, 정답에 더하기 하면된다 이방법이 왜 최적인지는 허프만코드 알고리즘과 동일하므로 이를 참고하면 된다. 2. 내코드 #include using namespace std; int ret,n; priority_queue pq; int main() { cin.tie(0); cin >> n; while (n--) { int tmp; cin ..