반응형 우선순위 큐23 [코드트리] 토끼와 경주 (삼성 SW 역량테스트 2023 상반기 오전 2번, B형) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 A형 전체 링크삼성 B형 전체 링크 2022 하반기 이후 문제 풀이 시간이 3시간 → 4시간으로 변경,A형 1문제 + B형 문제 1문제가 출제됩니다. 참고- B형 필수 : 우선순위 큐 Priority Queue- BOJ 10825 : 국영수 https://www.codetree.ai/training-field/frequent-problems/problems/rabit-and-race 2차원 좌표 N x M이 100,000 * 100,000이다. → 2차원 배열 선언 시, 메모리 초과토끼가 움직이는 거리 d → d 만큼 움직이면 시간 초과 따라서, 토끼 구조체에서 좌표를 관리하고, 효율적으로 움직여야 한다. 좌표를 관리할 구조체와 토끼.. 2024. 7. 28. Indexed Priority Queue - 우선순위 큐의 임의 원소 갱신, 변경 (update) SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 B형 전체 링크 참고- 우선순위 큐 Priority Queue- 우선순위 큐 응용 (1) - 두 개의 heap을 이용하여 중앙값 찾기- 우선순위 큐 응용 (2) - 최댓값, 최솟값 동시에 관리하기- 우선순위 큐 임의 원소 삭제- 우선순위 큐 임의 원소 삭제 최적화- 우선순위 큐 임의 원소 갱신, 변경 [수정] 항상감사합니다.님의 의견에 따라 방어코드가 필요한 것을 확인하였습니다.제 코드는 update할 index = updatehn이 updatehn * 2 == hn(힙의 현재 크기)인 경우 문제가 발생합니다. PRO 시험에 제 코드를 사용하시는 분들은 아래 추가된 글 참고 부탁드립니다. Reference code ver Inde.. 2022. 1. 13. BOJ 14427 : 수열과 쿼리 15 (Reference) 삼성 B형 전체 링크 https://www.acmicpc.net/problem/14427 B형에서는 Reference로 우선순위 큐 code가 주어진다. 하지만 STL(priority_queue) 사용이 가능하더라도, 갱신이 가능한 우선순위 큐는 직접 만들어야 한다. 여기서는 Reference 우선순위 큐로 문제를 풀었다. (Indexed Priority Queue, Heap) 해설은 이전 글을 참고하자. #include int N, M; typedef struct st { int value; int id; }HEAP; HEAP heap[100100]; int heapIdx[100100]; int heapSize; int isMin(HEAP a, HEAP b) { if (a.value < b.value).. 2021. 7. 3. BOJ 14427 : 수열과 쿼리 15 with 우선순위 큐 삼성 B형 전체 링크 https://www.acmicpc.net/problem/14427 참고 - BOJ 14427 : 수열과 쿼리 15 with 세그먼트 트리 우선순위 큐의 갱신을 이용하여 문제를 풀 수 있다. update를 위해 우선순위 큐를 최악의 값으로 초기화한다. for (int i = 0; i < 200100 /* heap size */; i++) heap[i].id = heap[i].value = 0x7fff0000; 처음의 값들은 순서대로 A1 ~ AN 이므로 heapIdx(id)를 각각 i = 1 ~ N으로 본다. for (int i = 1; i 1; i /= 2) { if (isMin(heap[i / 2], heap[i])) break; tmp = heap[i]; heap[i] = he.. 2021. 7. 3. 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 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. 이전 1 2 3 다음 반응형
