본문 바로가기
반응형

알고리즘/[PRO] 삼성 SW 역량 테스트 B형45

우선순위 큐 갱신 - 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.
인라인(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.
반응형

티스토리툴바