본문 바로가기
반응형

삼성 PRO60

최소 힙 - 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.
인라인(inline) 함수 - 삼성 SW 역량 시험 환경 삼성 B형 전체 링크 결론부터 이야기하면, 삼성 SW 역량에서 inline 함수는 쓸모없다. Visual Studio에서 inline 함수와 inline이 아닌 함수, 그리고 MACRO 함수의 속도를 비교해보자. 그리고 삼성 SW 역량 테스트 환경에서 비교해보겠다. 먼저 Visual Studio에서 inline 함수를 사용하려면 최적화 설정을 변경해야 한다. 솔루션 탐색기에서 마우스 오른쪽 버튼을 클릭한 후 속성으로 들어가보자. 구성 속성에서 C/C++ → 최적화를 클릭한 후 인라인 함수 확장에서 __inline만 확장을 선택한다. 이렇게 설정하지 않으면 inline 키워드를 추가해도 인라인 되지 않는다. Visual Studio에서 실행 시간을 확인하는 방법은 링크를 참고하자. 아래의 코드는 두 변수 .. 2021. 5. 19.
BOJ 9612 : Maximum Word Frequency 삼성 B형 전체 링크 www.acmicpc.net/problem/9612 해시 테이블을 이용하여 가장 빈도수가 높은 단어와 개수를 세보자. 같은 수의 단어가 있는 경우 사전 순으로 뒤에 있는 단어를 출력한다. 구조체에는 단어의 수와 실제 단어, 그리고 링크드 리스트를 위한 struct pointer가 필요하다. 메모리 풀 방식으로 연결하기 위해 POOL 메모리와 pcnt를 선언한다. typedef unsigned long ul; #define MAX_TABLE (1007) #define MAX_WORD (20 + 5) int N; typedef struct st { int count; char word[MAX_WORD]; struct st *next; }HASHTABLE; HASHTABLE hashTab.. 2021. 5. 9.
최적화) 삼성 C형 샘플 문제 : 블록 부품 맞추기 삼성 B형 전체 링크 삼성 C형 전체 링크 블록 부품 맞추기 문제를 더 최적화 해보자. 아래의 makeBlock에서 코드를 하나씩 지워보며 시간을 재보면 sort에서 비용이 많이 드는 것을 알 수 있다. int makeBlock(int module[][4][4]) { register int i, sum; bcnt1 = bcnt2 = mcnt1 = mcnt2 = 0; for (i = 0; i < 30000; i++) check1[i] = check2[i] = 0; makeHash(module); sort(match1, 0, mcnt1 - 1, isMinForMatch); sort(block1, 0, bcnt1 - 1, isMinForBlock); sort(match2, 0, mcnt2 - 1, isMinF.. 2021. 4. 3.
삼성 C형 샘플 문제 : 블록 부품 맞추기 삼성 B형 전체 링크 삼성 C형 전체 링크 참고 - 삼성 C형 샘플 문제 : 블록 부품 맞추기 최적화 swexpertacademy.com/main/sst/intro.do SW Expert Academy에서 C형 샘플 문제 블록 부품 맞추기를 풀어보자. 블록 부품 맞추기는 C형 샘플 문제지만 B형 유형으로 풀 수 있다. 여기서 필요한 개념은 2차원 배열의 해싱과 정렬(merge sort), 그리고 이분 탐색이다. 보통 어떤 데이터를 빠르게 찾고 싶은 경우, 정렬을 한 후에 이분 탐색을 하는 경우가 많다. 문제의 예시를 보자. 오른쪽의 블럭을 뒤집어서 맞춰 끼우면 모두 높이가 8인 완벽한 육면체가 된다. 총 30,000개의 블럭 중에 완성품의 합이 최대가 되도록 블럭을 맞춰야한다. 먼저 블럭 배열에 번호를 .. 2021. 3. 30.
BOJ 7662 : 이중 우선순위 큐 삼성 B형 전체 링크 www.acmicpc.net/problem/7662 참고 - 우선순위 큐 Priority Queue - 우선순위 큐 응용 (1) - 두 개의 heap을 이용하여 중앙값 찾기 - 우선순위 큐 응용 (2) - 최댓값, 최솟값 동시에 관리하기 - 우선순위 큐 임의 원소 삭제 - 우선순위 큐 임의 원소 삭제 최적화 - 우선순위 큐 임의 원소 갱신, 변경 가운데를 말해요에서 최대힙과 최소힙 두 개를 이용하여 중앙값을 유지시켰다. 이중 우선순위 큐도 마찬가지로 최대힙에서 최댓값을 관리하고 최소힙에서 최솟값을 관리하면 데이터의 최댓값과 최솟값을 O(1)만에 찾을 수 있다. (heap[1]로 접근하면 된다.) 그런데, 최소힙에서 삭제된 data를 최대힙에서 단순히 삭제할 수는 없다. (반대도 마찬.. 2021. 3. 24.
BOJ 20920 : 영단어 암기는 괴로워 (우선순위 큐 갱신 + Hash Table) 삼성 B형 전체 링크 www.acmicpc.net/problem/20920 단어를 저장하기 위해 해시 테이블을 사용한다. 회사에 있는 사람에서는 해시 테이블을 이용해 단어를 저장하고, 정렬하였다. 마찬가지로 외워야할 단어를 저장하고, count한 다음에 정렬해도 된다. 하지만, 여기에서는 우선순위 큐를 갱신하는 방법으로 문제를 풀어보겠다. 먼저 위에서 요구하는 우선순위를 보자. 자주 나오는 단어일수록 앞에 배치한다. 해당 단어의 길이가 길수록 앞에 배치한다. 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다 위의 우선순위에서 단어를 입력받을 때, heap에서 해당 단어의 횟수를 증가시킬 필요가 있다. 우선순위 큐를 이용하여 단어의 수를 update해보자. 단어를 저장하고, 저장된 단어의 있는지 체크.. 2021. 3. 21.
BOJ 18139 : Rush Hour Puzzle (해시, 2차원 배열 탐색) 삼성 B형 전체 링크 www.acmicpc.net/problem/18139 참고 - 해시 테이블 Hash Table - 해시 테이블 추가, 삭제, 수정, 검색 - 해시 응용 - 2차원 배열 탐색 - 해시 응용 - Rush Hour Puzzle (2차원 배열 탐색 응용) - 해시 테이블 성능 비교 내용을 번역해서 요약하면 아래와 같다. 1) 6 x 6 board에서 자동차가 최대 10개 존재한다. 2) 자동차는 1칸씩 움직이며, 길이가 2 또는 3이다. 3) 1번 자동차가 exit로 탈출해야 한다. 4) exit는 항상 3번째 줄의 오른쪽 끝이다. 따라서 1번 자동차는 항상 3번째 줄에 가로로 존재한다. 5) 최대 10칸까지 움직인다. 그 이상 움직여도 1번 자동차가 exit로 탈출 못하면 -1을 출력한다.. 2021. 3. 18.
Indexed Priority Queue - 우선순위 큐의 임의 원소 삭제 (2) : 최적화 삼성 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)으로 줄여보자. 아이디어는 다음과 같다. deleteId 함수에서 delhn = fin.. 2021. 3. 13.
반응형

티스토리툴바