반응형 priority queue29 BOJ 7662 : 이중 우선순위 큐 삼성 B형 전체 링크 www.acmicpc.net/problem/7662 참고 - 우선순위 큐 Priority Queue - 우선순위 큐 응용 (1) - 두 개의 heap을 이용하여 중앙값 찾기 - 우선순위 큐 응용 (2) - 최댓값, 최솟값 동시에 관리하기 - 우선순위 큐 임의 원소 삭제 - 우선순위 큐 임의 원소 삭제 최적화 - 우선순위 큐 임의 원소 갱신, 변경 가운데를 말해요에서 최대힙과 최소힙 두 개를 이용하여 중앙값을 유지시켰다. 이중 우선순위 큐도 마찬가지로 최대힙에서 최댓값을 관리하고 최소힙에서 최솟값을 관리하면 데이터의 최댓값과 최솟값을 O(1)만에 찾을 수 있다. (heap[1]로 접근하면 된다.) 그런데, 최소힙에서 삭제된 data를 최대힙에서 단순히 삭제할 수는 없다. (반대도 마찬.. 2021. 3. 24. BOJ 20920 : 영단어 암기는 괴로워 (우선순위 큐 갱신 + Hash Table) 삼성 B형 전체 링크 www.acmicpc.net/problem/20920 단어를 저장하기 위해 해시 테이블을 사용한다. 회사에 있는 사람에서는 해시 테이블을 이용해 단어를 저장하고, 정렬하였다. 마찬가지로 외워야할 단어를 저장하고, count한 다음에 정렬해도 된다. 하지만, 여기에서는 우선순위 큐를 갱신하는 방법으로 문제를 풀어보겠다. 먼저 위에서 요구하는 우선순위를 보자. 자주 나오는 단어일수록 앞에 배치한다. 해당 단어의 길이가 길수록 앞에 배치한다. 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다 위의 우선순위에서 단어를 입력받을 때, heap에서 해당 단어의 횟수를 증가시킬 필요가 있다. 우선순위 큐를 이용하여 단어의 수를 update해보자. 단어를 저장하고, 저장된 단어의 있는지 체크.. 2021. 3. 21. BOJ 2696 : 중앙값 구하기 알고리즘 문제 전체 링크 www.acmicpc.net/problem/2696 문제의 원리는 가운데를 말해요와 같다. 차이점은 매 tc마다 heap을 초기화 그리고 최초 입력을 받고 홀수 번째 입력부터 가운데 값을 출력 한 줄에 10개씩 출력 이다. #include int T, M; int minHeap[100100]; int minHn; int maxHeap[100100]; int maxHn; int maxPop(int* heap, int& hn) { int tmp, ret; ret = heap[1]; heap[1] = heap[hn]; heap[hn--] = -10001; for (int i = 1; i * 2 heap[i * 2] && heap[i] > heap[i * 2 + 1]) break; el.. 2021. 3. 20. Indexed Priority Queue - 우선순위 큐의 임의 원소 삭제 (2) : 최적화 삼성 B형 전체 링크 참고 - 우선순위 큐 Priority Queue - 우선순위 큐 응용 (1) - 두 개의 heap을 이용하여 중앙값 찾기 - 우선순위 큐 응용 (2) - 최댓값, 최솟값 동시에 관리하기 - 우선순위 큐 임의 원소 삭제 - 우선순위 큐 임의 원소 삭제 최적화 - 우선순위 큐 임의 원소 갱신, 변경 Indexed Priority Queue, Heap - 삭제 구현, 최적화 이전 글에서는 우선순위 큐의 임의 원소 삭제에 O(NlogN)의 비용을 O(N) + O(logN) ≒ O(N)으로 줄였다. 이제 memoization을 이용하여 O(N) + O(logN)을 O(1) + O(logN) ≒ O(logN)으로 줄여보자. 아이디어는 다음과 같다. deleteId 함수에서 delhn = fin.. 2021. 3. 13. Indexed Priority Queue - 우선순위 큐의 임의 원소 삭제 삼성 B형 전체 링크 참고 - 우선순위 큐 Priority Queue - 우선순위 큐 응용 (1) - 두 개의 heap을 이용하여 중앙값 찾기 - 우선순위 큐 응용 (2) - 최댓값, 최솟값 동시에 관리하기 - 우선순위 큐 임의 원소 삭제 - 우선순위 큐 임의 원소 삭제 최적화 - 우선순위 큐 임의 원소 갱신, 변경 Indexed Priority Queue, Heap - 삭제 구현 B형에서는 우선순위 큐를 이용해 문제를 풀어야 하는 경우가 많다. 우선순위 큐를 쓰면 임의의 값을 push해도 정렬을 유지할 수 있고, 가장 우선순위가 높은 값을 제거해도 정렬을 유지할 수 있다. 하지만 우선순위 큐를 쓰면 될 것 같은데, 애매한 상황이 하나가 있다. 우선순위는 낮지만, 특정 값을 제거해야하는 경우에는 우선순위.. 2021. 3. 13. BOJ 1655 : 가운데를 말해요 with 우선순위 큐 삼성 B형 전체 링크 알고리즘 문제 전체 링크 www.acmicpc.net/problem/1655 참고 - 우선순위 큐 Priority Queue - 우선순위 큐 응용 (1) - 두 개의 heap을 이용하여 중앙값 찾기 - 우선순위 큐 응용 (2) - 최댓값, 최솟값 동시에 관리하기 - 우선순위 큐 임의 원소 삭제 - 우선순위 큐 임의 원소 삭제 최적화 - 우선순위 큐 임의 원소 갱신, 변경 - BOJ 1655 : 가운데를 말해요 with 세그먼트 트리 가운데라는 값은 우선순위로 두기 굉장히 애매하다. 이유는 가장 높은 우선순위의 가운데와 최악의 가운데를 정의할 수 없기 때문이다. 만약 어떤 값들 중, 가운데 값을 pop한다고 하자. 그러면 heap[hn--] 에서 최악의 가운데 값을 넣어야 하는데, 이.. 2021. 2. 21. BOJ 10825 : 국영수 삼성 B형 전체 링크 www.acmicpc.net/problem/10825 정렬의 방법은 다양하지만 우선순위 큐 응용을 위해 힙으로 풀어보자. 우선순위가 높은 순은 다음과 같다. 1) 국어 점수가 높다. 2) 국어 점수가 같으면 영어 점수는 낮은 순. 3) 영어 점수까지 같으면 수학 점수가 높은 순. 4) 모두 같은 점수면 이름의 사전 순. 따라서 pop을 할 때, 최악의 input은 아래와 같다. heap[hn].kr = 0; /* 낮은 국어 점수 */ heap[hn].en = 0x7fff0000; /* 높은 영어 점수 */ heap[hn--].math = 0; /* 낮은 수학 점수 */ mystrcpy(heap[hn--].name, "zzzzzzzzzz"); /* 사전 순으로 가장 뒤의 이름 */ 우.. 2021. 2. 21. BOJ 11286 : 절댓값 힙 삼성 B형 전체 링크 www.acmicpc.net/problem/11286 우선순위가 최소 힙, 최대 힙보다 조금 더 까다롭다. 1) 절댓값이 가장 작으면 우선순위가 높다. 2) 같은 절댓값인 경우는 음수가 우선순위가 높다. 따라서, 최악의 값은 양수 중에 가장 큰 값이 된다. if / else if의 비교를 함수로 만들면 편하다. heap[hn--] = 0x7fff0000; /* 최악의 값은 양수 중 가장 큰 값 */ int abs(int x) { return (x > 0) ? x : -x; } int isMin(int a, int b) { if (abs(a) < abs(b)) return 1; /* 절댓값 중 작으면 우선순위가 크다 */ if (abs(a) == abs(b) && a < b) retu.. 2021. 2. 21. BOJ 11279 : 최대 힙 삼성 B형 전체 링크 www.acmicpc.net/problem/11279 우선순위 큐 설명은 링크를 참고하자. 링크를 보면, pop과 push에서 변경해야 할 곳은 총 4군데 이다. int pop(int* heap, int& hn) { ... heap[hn--] = 0x7fff0000; for (register int i = 1; i * 2 1; i /= 2) { if (heap[i / 2] heap[i * 2 + 1]) break; else if (heap[i * 2] > heap[i * 2 + 1]) { tmp = heap[i * 2]; heap[i * 2] = heap[i]; heap[i] = tmp; i = i * 2; } else { tmp = heap[i * 2 + 1]; heap[i * 2.. 2021. 2. 21. 이전 1 2 3 4 다음 반응형
