힙 썸네일형 리스트형 BOJ)2610 회의준비 문제: icpc.me/2610 각각의 컴포넌트에서 해당 컴포넌트에 속한 모든 정점으로 가는 최단거리들의 최댓값이 최소가 되는 정점들을 출력하는 문제이다. 각 정점들간의 최단거리는 플로이드 워셜을 이용하여 구해주면 되고 어떤 컴포넌트에 속한 정점에서 해당 컴포넌트에 속한 모든 정점으로 가는 최단거리들 중 최댓값을 힙에 저장하여 순서대로 답에 넣어주는 것으로 문제를 해결할 수 있다. 힙을 볼 때 이미 처리한 컴포넌트에 속한 정점은 지나쳐주어야하는데 이는 disjoint-set을 이용하면 간단하게 해결해줄 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859.. 더보기 BOJ)1202 보석 도둑 문제: icpc.me/1202 가장 가격이 많이 나가는 보석을 최대한 많이 담아야 원하는 답을 구할 수 있는건 그리디하게 알 수 있다. 그렇기 때문에 우리는 가장 가격이 많이 나가는 보석을 먼저 보며 lower_bound를 이용하여 현재 그 보석을 담을 수 있는 가방이 있느지 확인해주면 된다. 1234567891011121314151617181920212223242526272829303132#include #include #include #include using namespace std;int n, k, x, y;long long r;int main() { scanf("%d%d", &n, &k); priority_queue pq; for (int i = 0; i 더보기 BOJ)1826 연료 채우기 문제:icpc.me/1826 1km를 가는데 1L의 연료가 필요하고 현재 가진 연료량과 목적지까지의 거리 그리고 각 주유소의 정보가 주어질 때 충전횟수를 최소화하여 목적지에 도착하는 충전횟수를 출력하는 문제이다. 우선 주유소의 정보를 받아 거리를 기준으로 sort한 뒤 내가 현재 갈 수 있는 거리보다 가까운 거리에 있는 모든 주유소의 정보를 받아와 채울 수 있는 연료량을 heap에 저장한다. 이후 그리디하게 갈 수 있는 주유소중 가장 큰 연료량을 가지는 주유소를 선택해나가면 문제를 해결 할 수 있다. 123456789101112131415161718192021222324252627#include #include #include using namespace std;priority_queue pq;int n.. 더보기 BOJ)2075 N번째 큰 수 문제:icpc.me/2075 N^2개의 수가 들어올 때 N번째로 큰 수를 구하는 문제이다. N이 최대 1500 밖에 안들어오므로 단순히 값을 다 받아서 정렬해주는 N^2logN의 해법으로 해결할 수 있다. 하지만 메모리제한이 10MB이므로 힙을 이용하여 수를 받을 때 마다 큰 수 N개만큼만 저장해주고 그 수들중 가장 작은 수와 들어오는 수를 비교를하여 힙을 관리해주면 된다. 123456789101112131415161718192021222324#include #include #include using namespace std;int n, x;priority_queue pq;int main() { scanf("%d", &n); for (int i = 0; i 더보기 BOJ)1966 프린터 큐 문제: icpc.me/1966 큐에서 priority가 가장 높지 않으면 뽑은 뒤 맨 뒤로 보낼 때 m번째 수는 몇번째로 뽑히는지 출력하는 문제이다. N이 100밖에 되지 않으므로 N^2 시뮬레이션을 돌려주면 된다. 들어오는 모든 수를 priority queue 와 queue에 넣어준 후 pq의 top과 queue의 front값이 같을 때만 값을 뽑아주면 된다. 1234567891011121314151617181920212223242526272829303132#include #include #include using namespace std;int t, n, m, x, r;int main() { scanf("%d", &t); while (t--) { r = 0; queue qu; priority_queu.. 더보기 BOJ)11338 XOR Sum 문제: icpc.me/11338 n개의 쿼리가 주어질 때 2가지 쿼리에 따라서 문제를 해결하는 문제이다. insert 쿼리는 리스트에 숫자를 추가하는것이며 print 쿼리는 리스트 중에 상위 K숫자를 XOR한 값을 출력하는 문제이다. 우리는 매 print마다 리스트에서 XOR을 할 경우 시간초과가 나므로 insert 될 때 마다 모든 값을 XOR해준 뒤 minheap을 이용하여 리스트 숫자가 K를 초과할때 마다 최솟값을 XOR해준다. 이는 A^X^X=A가 되는 원리를 이용하는 풀이이다. 1234567891011121314151617181920212223242526272829303132#include #include #include using namespace std;char a[7];int t, m, k.. 더보기 BOJ)1766 문제집 문제: icpc.me/1766 문제집을 푸는 순서가 주어지는데 이때 가능하면 쉬운 문제부터 풀어야 할 경우 문제를 푸는 순서를 출력하는 문제이다. 우리는 문제집을 푸는 순서가 주어질 때 topological sort를 통하여 순서를 출력할 수 있다. 하지만 가능하면 쉬운 문제를 풀어야 하니 topology가 여러개일 경우 작은 순서를 먼저 출력해줘야 한다. 이는 min heap을 통하여 해결 가능하다. 123456789101112131415161718192021222324252627282930313233#include #include #include #include #define MAX_N 32000using namespace std;int n, m, a, b, in[MAX_N + 1];vector vt.. 더보기 BOJ)1666 최대 증가 직사각형 집합 문제: icpc.me/1666 여러 직사각형이 주어졌을 때 이중 몇개의 직사각형을 골라서 집합을 만들것이다. 이때 집합의 조건은 집합의 임의의 두 원소를 선택했을 때 두 직사각형중 한 직사각형이 다른 한 직사각형보다 오른쪽 위에 있어야한다는 조건이다. 우선 각 원소를 왼쪽 아래 점의 x좌표 기준으로 스위핑하여 문제를 푸려고한다. 우리는 각 원소를 비교해나가며 쿼리를 처리하며 세그먼트 트리에 업데이트 할 것인데 이 때 비교는 왼쪽 아래 점과 하며 업데이트는 오른쪽 윗 점을 할것이다. x좌표 기준으로 정렬을 했기 때문에 우리는 세그먼트 트리에 y좌표의 위치에 업데이트 할 것이다. 이때 좌표압축을 사용해 노드를 줄인다. 하지만 우리는 비교는 왼쪽 아래 점 기준으로 하며 정렬도 왼쪽 아래 점 기준으로 하지만 업.. 더보기 이전 1 다음