본문 바로가기
반응형

우선순위 큐23

최소 힙 - B형 Reference 코드 (우선순위 큐) 삼성 B형 전체 링크 Reference 코드의 우선순위 큐는 아래와 같다. #include #define MAX_SIZE 100 int heap[MAX_SIZE]; int heapSize = 0; void heapInit(void) { heapSize = 0; } int heapPush(int value) { if (heapSize + 1 > MAX_SIZE) { printf("queue is full!"); return 0; } heap[heapSize] = value; int current = heapSize; while (current > 0 && heap[current] < heap[(current - 1) / 2]) { int temp = heap[(current - 1) / 2]; heap[(.. 2021. 6. 5.
BOJ 5896 : 효율적으로 소 사기 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/5896 우선순위 큐를 이용하여 문제를 풀 수 있다. 아래의 경우에 대해서 생각해보자. 1) 쿠폰을 사용할 수 없는 경우. 모든 소의 원가에 대해 가장 가격이 낮은 소부터 산다. 2) 모든 소에 대해 쿠폰을 사용할 수 있는 경우. 모든 소의 쿠폰 적용가에 대해 가장 가격이 낮은 소부터 산다. 두 경우는 쉽게 해결할 수 있다. 문제는 쿠폰의 수가 0 < K < N인 경우이다. 쿠폰을 사용하였을 때, 가격이 가장 작은 소부터 고르고, 남은 소 중에는 원가에서 가장 싼 가격만 고를 경우 아래와 같은 문제가 생길 수 있다. 먼저 돈이 7원, 쿠폰은 1장만 쓸 수 있는 경우를 보자. 소1 : 원가 - 10원, 쿠폰가 - 5원 소2 .. 2021. 5. 18.
BOJ 1715 : 카드 정렬하기 알고리즘 문제 전체 링크 www.acmicpc.net/problem/1715 카드 비교 횟수를 줄이기 위해서는 가장 작은 수의 두 카드를 비교해야한다. 그리고 카드를 합친다. (+ 횟수를 누적한다.) 그러면 다시 남은 카드(+ 합친카드 포함) 중에서 가장 작은 수의 두 카드를 비교해야한다. 따라서, 우선순위 큐를 이용한다. 가장 작은 두 카드는 두 번 pop하면 얻을 수 있고, 합친 카드를 우선순위 큐에 넣어도 우선순위 큐를 두 번 pop하면 가장 작은 두 카드를 구할 수 있다. #include int N; int heap[100100]; int hn; int pop(int* heap, int& hn) { int tmp, ret; ret = heap[1]; heap[1] = heap[hn]; heap[h.. 2021. 4. 9.
BOJ 7662 : 이중 우선순위 큐 A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 B형 전체 링크 www.acmicpc.net/problem/7662 참고- 우선순위 큐 Priority Queue- 우선순위 큐 응용 (1) - 두 개의 heap을 이용하여 중앙값 찾기- 우선순위 큐 응용 (2) - 최댓값, 최솟값 동시에 관리하기- 우선순위 큐 임의 원소 삭제- 우선순위 큐 임의 원소 삭제 최적화- 우선순위 큐 임의 원소 갱신, 변경  가운데를 말해요에서 최대힙과 최소힙 두 개를 이용하여 중앙값을 유지시켰다. 이중 우선순위 큐도 마찬가지로 최대힙에서 최댓값을 관리하고 최소힙에서 최솟값을 관리하면데이터의 최댓값과 최솟값을 O(1)만에 찾을 수 있다. (heap[1]로 접근하면 된다.)그런데, 최소힙에서 삭제된 dat.. 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) : 최적화 A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 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)으로 줄여보자.아이디어는 다음과.. 2021. 3. 13.
Indexed Priority Queue - 우선순위 큐의 임의 원소 삭제 SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 B형 전체 링크 참고- 우선순위 큐 Priority Queue- 우선순위 큐 응용 (1) - 두 개의 heap을 이용하여 중앙값 찾기- 우선순위 큐 응용 (2) - 최댓값, 최솟값 동시에 관리하기- 우선순위 큐 임의 원소 삭제- 우선순위 큐 임의 원소 삭제 최적화- 우선순위 큐 임의 원소 갱신, 변경 Indexed Priority Queue, Heap - 삭제 구현 B형에서는 우선순위 큐를 이용해 문제를 풀어야 하는 경우가 많다.우선순위 큐를 쓰면 임의의 값을 push해도 정렬을 유지할 수 있고,가장 우선순위가 높은 값을 제거해도 정렬을 유지할 수 있다.하지만 우선순위 큐를 쓰면 될 것 같은데, 애매한 상황이 하나가 있다.우선순위는 낮.. 2021. 3. 13.
BOJ 1655 : 가운데를 말해요 with 우선순위 큐 SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 B형 전체 링크알고리즘 문제 전체 링크 www.acmicpc.net/problem/1655 참고- 우선순위 큐 Priority Queue- 우선순위 큐 응용 (1) - 두 개의 heap을 이용하여 중앙값 찾기- 우선순위 큐 응용 (2) - 최댓값, 최솟값 동시에 관리하기- 우선순위 큐 임의 원소 삭제- 우선순위 큐 임의 원소 삭제 최적화- 우선순위 큐 임의 원소 갱신, 변경- BOJ 1655 : 가운데를 말해요 with 세그먼트 트리  가운데라는 값은 우선순위로 두기 굉장히 애매하다.이유는 가장 높은 우선순위의 가운데와 최악의 가운데를 정의할 수 없기 때문이다. 만약 어떤 값들 중, 가운데 값을 pop한다고 하자. 그러면 heap[hn.. 2021. 2. 21.
반응형

티스토리툴바