본문 바로가기
반응형

머지 소트6

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 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 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.
B형 필수 정렬 : 머지 소트 Merge Sort 삼성 B형 전체 링크 B형에서는 Quick 정렬을 Reference 코드로 제공한다. 하지만, Quick은 최악의 경우 O(N2)이므로, 어떤 상황에서도 O(NlogN)인 Merge Sort를 익혀두자. Merge Sort는 반으로 나누어서, 왼쪽을 정렬하고, 오른쪽을 정렬한 후, 합치는 방법으로 정렬을 한다. 왼쪽을 정렬할 때는, 다시 반으로 나누어서, 왼쪽, 오른쪽 정렬하고 합친다. 오른쪽도 마찬가지로 ... 즉, 재귀 함수를 이용해서 정렬하게 된다. start >= end면 더 이상 정렬할 수 없으므로 종료 조건으로 사용한다. void sort(int start, int end) { int mid; if (start >= end) return; mid = (start + end) >> 1; /* 절.. 2021. 2. 16.
반응형

티스토리툴바