본문 바로가기
반응형

정렬9

BOJ 15688 : 수 정렬하기 5 with In-Place Sort 알고리즘 문제 전체 링크 삼성 C형 전체 링크 https://www.acmicpc.net/problem/15688 참고 - BOJ 2751 : 수 정렬하기 2 with 계수 정렬 (Counting Sort) 만약 배열 a의 크기가 매우 크지만 원소의 종류는 매우 적다면, count와 countSum의 배열의 크기는 작아진다. 따라서 이 경우에는 a의 원소의 종류만큼만 필요하게 되고 추가적인 메모리가 거의 없이 in-place 처럼 sorting이 가능하다. 이상적인 In Place 정렬은 다음과 같다. 함수 스택에서 약간의 메모리만 사용할 뿐 추가적인 메모리 없이 a[]에서 서로 교환한다. void inPlaceSort(int a[], int size) { int count[MAX + 10] = { 0 .. 2023. 7. 29.
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 2751 : 수 정렬하기 2 with 계수 정렬 (Counting Sort) 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/2751 주어지는 숫자가 -1,000,000 ~ 1,000,000이기 때문에 0 ~ 2,000,000으로 바꾼다. 그리고 a[0 ~ 2,000,000]에는 각 원소의 개수를 증가시키고, 출력할 때는 작은 값부터 원소의 개수만큼 출력하고 다음으로 넘어간다. #include #define MINUS (1000000) int N; int a[1000000 + MINUS + 1000]; int main(void) { scanf("%d", &N); for (int i = 0; i < N; i++) { int tmp; scanf("%d", &tmp); a[tmp + MINUS]++; } for (int i = 0; i 2023. 1. 22.
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.
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 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.
반응형

티스토리툴바