본문 바로가기
반응형

merge sort10

BOJ 8983 : 사냥꾼 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/8983 참고 - 머지 소트 Merge Sort 어떤 동물이 사대에서 잡을 수 있는 동물이라면, 이 동물을 기준으로 가장 가까운 사대만 확인하면 된다. 즉, 동물을 기준으로 왼쪽과 오른쪽 사대에 대해서만 거리를 계산해 L과 비교하면 된다. 왼쪽과 오른쪽 사대가 동물을 사냥할 수 없다면, 다른 사대는 더 멀리 있으므로 검사할 필요가 없다. 사대의 좌표(= x)를 작은 순으로 정렬하고, 동물도 x 좌표를 기준으로 정렬한다. 모두 정렬했으니, 사대의 좌표가 animal보다 가장 가깝게 작은 곳을 찾을 수 있다. while (index != M - 1 && place[index + 1] 2023. 1. 25.
BOJ 11004 : K번째 수 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/11004 O(NlogN) 정렬로 정렬한 후, A[K]를 출력하면 된다. 여기서는 merge sort를 사용하였다. 이때, K는 입력을 받은 후, 1을 빼야한다. #include int N, K; int A[5050000]; int B[5050000]; void merge(int* A, int start, int end) { int mid, i, j, k; mid = (start + end) >> 1; i = start; j = mid + 1; k = 0; while (i 2021. 7. 21.
최적화) 삼성 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 2467, 2470 : 두 용액 알고리즘 문제 전체 링크 www.acmicpc.net/problem/2467 www.acmicpc.net/problem/2470 BOJ 2467은 입력이 정렬이 되어서 들어오는 차이가 있다. 그 외 풀이는 BOJ 2470과 같다. B형에서 어떤 조건을 만족하는 값을 찾으려면 대부분 정렬을 한 후, 이분 탐색으로 찾는다. 이분 탐색 외에도 답을 찾는 테크닉 중 하나가 투 포인터 알고리즘이다. 포인터(index) 2개를 이용하여 효율적으로 원하는 답을 찾는다. 두 용액 문제는 모든 배열의 값 2개 중 합이 0에 가까운 값 2개를 찾는다. 용액이 모두 양수라면 가장 작은 두 값이, 모두 음수라면 가장 큰 두 값이 답이 된다. 문제는 양수와 음수가 있는 경우이다. 이 경우는 가장 작은 값과 가장 큰 값을 더해보.. 2021. 3. 29.
BOJ 7785 : 회사에 있는 사람 (Hash Table + Merge Sort) 삼성 B형 전체 링크 www.acmicpc.net/problem/7785 이름을 입력받으면, 아래의 DB 배열에 저장하고 in = 1로 두자. typedef struct st { char name[6]; int in; }DB; DB에 저장하고 이름을 hashing하여 HashTable에 저장하는데, 이때, DB를 포인터로 가르키도록 하자. typedef struct st2 { DB *db; struct st2 *next; }HASH; 즉, Hash에서 db를 보고 있으므로, 포인터로 접근하여 in = 0으로 바꿀 수 있게 된다. DB 자체는 배열로 유지하되, in을 Hash를 통해 포인터로 값을 바꾼다. input = 'enter'면 Hash 저장 및 in = 1, input = 'leave'면 Hash.. 2021. 2. 18.
BOJ 1764 : 듣보잡 (Hash Table + Merge Sort) 삼성 B형 전체 링크 www.acmicpc.net/problem/1764 듣도 못한 사람의 수 N명, 보도 못한 사람의 수 M명 중 두 명단에 모두 포함되는 사람의 수를 찾고, 사전순으로 출력해야 한다. 두 명단에 포함 → Hash Table 사전순 출력 → Merge Sort 꼭 이렇게 풀 필요는 없지만, B형 연습을 위해 Hash Table + Merge Sort로 풀어보자. B형에서는 string 라이브러리를 사용할 수 없으므로, strcmp와 strcpy는 직접 만들어야 된다. (가끔 코드로 제공) void mystrcpy(char *a, char *b) { while (*a++ = *b++); } int mystrcmp(const char *a, const char *b) { while (*a .. 2021. 2. 17.
BOJ 11728 : 배열 합치기 알고리즘 문제 전체 링크 www.acmicpc.net/problem/11728 Merge Sort에서 정렬된 배열을 합칠 때, 사용하는 merge 함수를 변형해서 사용하면 된다. #include int N, M; int a[1000100]; int b[1000100]; int main(void) { scanf("%d %d", &N, &M); for (int i = 0; i < N;i++) scanf("%d", &a[i]); for (int i = 0; i < M;i++) scanf("%d", &b[i]); int i, j; i = j = 0; while (i < N && j < M) { /* 둘 중 작은 것을 먼저 출력 */ if (a[i] 2021. 2. 17.
BOJ 2751 : 수 정렬하기 2 알고리즘 문제 전체 링크 www.acmicpc.net/problem/2751 참고 - 머지 소트 Merge Sort 여러 정렬 방법이 있겠지만, 여기에서는 merge sort로 풀어보자. #include int N; int a[1000000 + 50000]; int b[1000000 + 50000]; void merge(int start, int end) { int mid, i, j, k; mid = (start + end) >> 1; i = start; j = mid + 1; k = 0; while (i 2021. 2. 16.
반응형

티스토리툴바