반응형 priority queue29 BOJ 11286 : 절댓값 힙 (priority_queue, compare) 삼성 B형 전체 링크 https://www.acmicpc.net/problem/11286 절댓값 힙 문제를 STL을 적용해서 풀어보자. 위 링크에서 절댓값에 대한 우선순위를 아래와 같이 정의하였다. int isMin(int a, int b) { if (abs(a) chil.. 2021. 6. 21. BOJ 1927 : 최소 힙 (priority_queue, compare) 삼성 B형 전체 링크 https://www.acmicpc.net/problem/1927 STL을 이용해서 최대 힙을 풀었다. 이제 우선순위를 변경하는 방법을 알아보자. 기본적으로 정의된 priority_queue가 최대 힙이었으므로, compare를 만들어서 우선순위를 변경한다. operator를 오버로딩하여 최소 힙이 되도록 변경한다. 우선순위 큐의 operator는 parent와 child를 비교하여 true인 경우 swap한다. 따라서 parent > child → parent가 크면 swap → parent가 가장 작아질 때 까지 swap 이 되어 최소 힙이 된다. struct compare { bool operator()(const int& parent, const int& child) cons.. 2021. 6. 19. BOJ 11279 : 최대 힙 (priority_queue) 삼성 B형 전체 링크 https://www.acmicpc.net/problem/11279 우선순위 큐의 문제인 최대 힙을 STL - queue(priority_queue)로 풀어보자. 먼저 priority_queue의 메서드는 아래의 4개가 있다. push() pq에 원소를 넣는다. pop() pq에 원소를 뺀다. top() pq에서 가장 우선순위가 높은 값을 return 한다. (pure한 코드에서 heap[1]과 동일) size() pq의 크기를 return 한다. empty() pq가 비어있으면 true, 아니면 false를 return 한다. clear() clear가 없다. pure한 코드와 다른 점은, pq.pop()이 값을 리턴하지는 않는다. 원소를 빼기만 한다. pop이 void로 만들어져.. 2021. 6. 19. 우선순위 큐 갱신 - B형 Reference 코드 삼성 B형 전체 링크 B형 reference 코드의 우선순위 큐는 최소 힙만 주어져있다. 이번에는 우선순위 큐의 갱신을 알아보자. (Indexed Priority Queue, Heap) (삭제의 경우는 갱신 후 pop을 하면 되므로 필요시 적절히 코드를 수정하자.) 풀어볼 문제는 BOJ : 20920 영단어 암기는 괴로워이다. reference 코드에서 우선순위를 비교하는 곳을 구조체에 대한 우선순위로 수정한다. 1) heapPush의 while (current > 0 && heap[current] 0 && isPriority(heap[current], heap[(current - 1) / 2])) /* 우선순위 변경 */ { HEAP temp = heap[(current - 1) / 2]; /* int.. 2021. 6. 9. 구조체 힙 - B형 Reference 코드 (우선순위 큐) 삼성 B형 전체 링크 B형 reference 코드의 우선순위 큐는 최소 힙만 주어져있다. 코드 변경을 최소화해서 구조체 힙을 풀어보자. reference 코드에서 우선순위를 비교하는 곳을 구조체에 대한 우선순위로 수정한다. 1) heapPush의 while (current > 0 && heap[current] HEAP */ int heapSize; void mystrcpy(char *a, const char *b) { while (*a++ = *b++); } int mystrcmp(const char *a, const char *b) { while (*a && *a == *b) ++a, ++b; return *a - *b; } int isMin(HEAP a, HEAP b) /* int -> HEAP */.. 2021. 6. 8. 최대 힙, 절댓값 힙 - B형 Reference 코드 (우선순위 큐) 삼성 B형 전체 링크 B형 reference 코드의 우선순위 큐는 최소 힙만 주어져있다. 코드 변경을 최소화해서 최대 힙과 절댓값 힙을 풀어보자. reference 코드에서 우선순위를 비교하는 곳을 수정하면 된다. 1) heapPush의 while (current > 0 && heap[current] heap[child]) /* 우선순위 변경 */ { break; } int temp = heap[current]; heap[current] = heap[child]; heap[child] = temp; current = child; } return 1; } int main(void) { scanf("%d", &N); for (int i = 0; i < N;i++) { int x; scanf("%d", &x).. 2021. 6. 5. 최소 힙 - 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. 이전 1 2 3 4 다음 반응형
