본문 바로가기

삼성 PRO60

Indexed Priority Queue - 우선순위 큐의 임의 원소 삭제 SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기) 삼성 B형 전체 링크 참고- 우선순위 큐 Priority Queue- 우선순위 큐 응용 (1) - 두 개의 heap을 이용하여 중앙값 찾기- 우선순위 큐 응용 (2) - 최댓값, 최솟값 동시에 관리하기- 우선순위 큐 임의 원소 삭제- 우선순위 큐 임의 원소 삭제 최적화- 우선순위 큐 임의 원소 갱신, 변경 Indexed Priority Queue, Heap - 삭제 구현 B형에서는 우선순위 큐를 이용해 문제를 풀어야 하는 경우가 많다.우선순위 큐를 쓰면 임의의 값을 push해도 정렬을 유지할 수 있고,가장 우선순위가 높은 값을 제거해도 정렬을 유지할 수 있다.하지만 우선순위 큐를 쓰면 될 것 같은데, 애매한 상황이 하나가 있다.우선순위는 낮.. 2021. 3. 13.

해시 응용 : 2차원 배열 탐색 삼성 B형 전체 링크 참고 - 해시 테이블 Hash Table - 해시 테이블 추가, 삭제, 수정, 검색 - 해시 응용 - 2차원 배열 탐색 - 해시 응용 - Rush Hour Puzzle (2차원 배열 탐색 응용) - 해시 테이블 성능 비교 아래와 같은 15x15 2차원 배열에서 오른쪽의 4x4 조각이 총 몇 개 있는지 찾아보자. 실제 B형 문제라면, 아래의 코드에서 findPiece 함수를 만들면 된다. #include int N = 15; int M = 4; char MAP[15][15] = { { 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, }, { 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, }, { 0, 0, 1, 0, 0.. 2021. 3. 9.

데이터의 추가, 삭제, 수정, 검색 - 해시 테이블 응용 삼성 B형 전체 링크 참고 - 해시 테이블 Hash Table - 해시 테이블 추가, 삭제, 수정, 검색 - 해시 응용 - 2차원 배열 탐색 - 해시 응용 - Rush Hour Puzzle (2차원 배열 탐색 응용) - 해시 테이블 성능 비교 해시 테이블의 기본을 응용하여, 추가/삭제/수정에 대해 알아보자. 어떤 게임의 DB에 아래와 같은 데이터가 있다고 가정해보자. 이 게임은 ID가 중복으로 있을 수 있다. 운영자는 이 DB를 관리해야하는데, 다음과 같은 기능이 필요하다. 1) 새로운 DB를 추가. 2) 현재 DB 중 특정 DB 삭제. (ID가 xxx인 DB 삭제, JOB이 wizard인 DB 삭제 등) 3) 현재 DB 중 특정 DB 수정. (JOB이 yyy인 DB에서 SERVER를 nova로 변경 등.. 2021. 2. 28.

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.

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.

B형 필수 : 우선순위 큐 Priority Queue A형 필수 알고리즘을 체계적으로 배우고 싶다면? (인프런 바로가기) 삼성 B형 전체 링크 참고 - 우선순위 큐 Priority Queue- 우선순위 큐 응용 (1) - 두 개의 heap을 이용하여 중앙값 찾기- 우선순위 큐 응용 (2) - 최댓값, 최솟값 동시에 관리하기- 우선순위 큐 임의 원소 삭제- 우선순위 큐 임의 원소 삭제 최적화- 우선순위 큐 임의 원소 갱신, 변경 B형에서 Merge Sort는 마지막에 이분 탐색을 위해 필요한 경우가 많다. 그리고 '무언가'를 push해주고, 그 중 가장 우선순위가 높은 '무언가'를 pop하면서,순서를 유지하고 싶을 때는 우선순위 큐를 이용해야된다. 요즘 B형에서는 HashTable + 우선순위 큐 모두 사용해야하는 경우가 많으므로, 우선순위 큐에 대해서 익혀.. 2021. 2. 19.

이전 1 2 3 4 5 6 7 다음

티스토리툴바