반응형 우선순위큐7 백준 1202번 보석 도둑 - C++(cpp) 풀이 + 그림 설명 1. 용량이 적은 가방부터 채운다. 2. 가방에 담을 수 있는 보석 중 가격이 가장 높은 것을 담는다. 3. 남은 가방에 대해 1-2를 반복한다. 1. 용량이 작은 가방부터 채운다. 한 가방에는 한 개의 보석만 담을 수 있으므로 그리디 하게 풀 수 있는 상황이다. 용량이 적은 가방에 들어가지 못한 보석이 용량이 큰 가방에는 들어갈 수도 있다. 반대로 용량이 큰 가방에 들어가지 못한 보석이 용량이 적은 가방에는 들어갈 일은 없다. 따라서 용량이 작은 가방부터 최선으로 채워나가면 최선의 결과를 얻을 수 있음이 보장된다. 2. 가방에 담을 수 있는 보석 중 가격이 가장 높은 것을 담는다. 먼저 용량이 C인 가방에 담을 수 있는 보석들을 걸러내기 위해 보석을 무게 순으로 정렬한다. 아래와 같은 상황이고, 가방의.. 2022. 1. 28. 백준 7662번 이중 우선순위 큐 - C++(cpp) 풀이 문제 제목에서부터 알 수 있듯이 우선순위 큐를 써야 하는데, 스위프트에는 라이브러리로 우선순위 큐를 제공하지 않아서 C++로 풀었다. 1. 최댓값은 최댓값 큐에서 찾는다. 2. 최솟값은 최솟값 큐에서 찾는다. 3. 반대쪽 큐에서 제거된 값인지 구별하기 위해, map에 해당 숫자가 현재 몇 개 남아있는지 기록한다. 먼저 최대값과 최솟값을 모두 알아내야 하므로 우선순위 큐를 2개 운영해야 한다. 하나는 최댓값용, 하나는 최솟값용으로. 근데 이렇게 되면 삭제를 할 때 문제가 된다. 최솟값을 삭제하라는 쿼리가 들어오면, 최솟값 큐에서 pop을 할 것이다. 근데 이 최솟값이 최댓값 큐에는 남아있게 된다. 따라서 반대 큐에서 삭제 여부를 알 수 있도록, 어떤 수 x가 현재 몇 개 남아 있는지를 기록해두어야 한다. .. 2022. 1. 14. 이전 1 2 다음 반응형
