반응형 힙10 [코드트리] 토끼와 경주 (삼성 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. 구조체 힙 - 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. 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 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(hea.. 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. BOJ 1927 : 최소 힙 삼성 B형 전체 링크 www.acmicpc.net/problem/1927 우선순위 큐 설명은 링크를 참고하자. #include int N; int heap[100100]; int hn; int pop(int* heap, int& hn) { register int tmp, ret; ret = heap[1]; heap[1] = heap[hn]; heap[hn--] = 0x7fff0000; for (register int i = 1; i * 2 1; i /= 2) { if (heap[i / 2] = 1; i /= 2) 최소 힙이지만, x가 자연수라는 조건에 의해서 얼떨결에 통과하게 되는 것이므로, i > 1이란 것을 잘 기억해두자. i = 1인 경우 부모 node가 없으므로, i > 1까지만 갱신하면 된다. 2021. 2. 21. 이전 1 2 다음 반응형
