1. 과제
백준 정렬 2750번 문제
2750번 문제를 합병정렬을 이용해 구현하는 방식으로 해결해보았다.
2. 참고한 사항 / 중요 사항
1) merge_sort 함수는 분할해주는 역할
void merge_sort(int arr[], int sorted[], int left, int right) {
int mid;
if (left < right) {
mid = (left + right) / 2;
// 분할
merge_sort(arr, sorted, left, mid); // 왼쪽 부분
merge_sort(arr, sorted, mid + 1, right); // 오른쪽 부분
// 병합하며 정렬
merge(arr, sorted, left, mid, right);
}
}merge_sort 함수에서는 left와 right 값을 가지고 mid 값을 구하고, 이 세 가지 값을 이용해 left ~ mid까지 왼쪽 부분, mid + 1 ~ right 까지 오른쪽 부분으로 분할한다.
그 후 merge 함수(실제로 병합정렬을 진행하는 부분)를 호출해서 이 함수의 left부터 right까지의 병합정렬을 진행시킨다.
2) merge 함수는 분할된 해당 부분을 왼쪽 부분, 오른쪽 부분을 나눠서 실제로 병합정렬을 진행하는 부분
void merge(int arr[], int sorted[], int left, int mid, int right) {
int i, j, k, l;
i = left; // 왼쪽 부분의 포인터 인덱스
j = mid + 1; // 오른쪽 부분의 포인터 인덱스
k = left; // 정렬된 배열에 넣을 인덱스
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) // 왼쪽 부분의 맨 앞쪽 값 <= 오른쪽 부분의 맨 앞쪽 값
sorted[k++] = arr[i++];
else
sorted[k++] = arr[j++];
}
if (i > mid)
for (l = j; l <= right; l++)
sorted[k++] = arr[l];
else
for (l = i; l <= mid; l++)
sorted[k++] = arr[l];
for (l = left; l <= right; l++)
arr[l] = sorted[l];
}merge 함수에서는
왼쪽 부분의 포인터 인덱스를 가리키는 i 변수 (left)
오른쪽 부분의 포인터 인덱스를 가리키는 j 변수 (mid + 1)
정렬되는 배열의 인덱스를 가리키는 k 변수 (left)
한 쪽이 다 끝나면 나머지 쪽을 다 넣기 위해 필요한 l 변수
가 필요하다.
왼쪽 부분의 맨 앞쪽 값이 오른쪽 부분의 맨 앞쪽 값보다 작은지 큰지를 통해
sorted의 k번째 자리에 그 값을 넣고, k를 한 칸 이동시키고 그 값을 넣은 쪽의 인덱스를 한 칸 이동시킨다
그리고 한 쪽이 다 끝나게 되면, 나머지쪽을 sorted 배열에 마저 다 넣는다!
3) N = 1일 때도 고려해야!
N = 1일 때를 고려하지 않아서 99%까지 가고 '틀렸습니다'가 떴다. 막막해서 결국 질문을 올렸는데 한 분께서 N = 1 일 때도 고려해야 한다고 말씀해주셨다. 내가 이때 구현한 코드로는, merge_sort(arr, sorted, 0, 0)이 호출되는데 left < right이 false라서 sorted에 아무 작업을 하지 않고 함수가 반환된다고 하셨다. 이를 해결해보기 위해 나는 일단 직접 해결하는 식으로 해결을 해보았다.
// 별로 안 좋은 해결 방법
void merge_sort(int arr[], int sorted[], int left, int right) {
int mid;
if (left == right) // N = 1일 때를 처리
sorted[0] = arr[0];
if (left < right) {
mid = (left + right) / 2;
// 분할
merge_sort(arr, sorted, left, mid); // 왼쪽 부분
merge_sort(arr, sorted, mid + 1, right); // 오른쪽 부분
// 병합하며 정렬
merge(arr, sorted, left, mid, right);
}
}left == right 라면 sorted[0] = arr[0]으로 대입하게 했더니 정답이라고 나오긴 했다. 하지만 이 방법이 최선의 방법인지는 잘 모르겠어서 추가 질문을 드렸는데, 이 방법은 좋은 방법이 아니라고 하셨다.
left == right가 N = 1일 때만 발생하는 것이 아니고 모든 N에 대해 분할하면서 내려가면 발생할 수 밖에 없다고 한다.
따라서 N > 1 일 때만 merge_sort를 호출하거나
sort 배열을 merge 함수 안에서만 관리하고 merge가 끝난 이후에 arr에 다시 대입하면 되는 방법이 깔끔한 방법이라고 한다!
그래서 N > 1 일 때는 딱히 정렬할 일이 없으므로 그 수를 출력시키고 (출력 안 시키면 또 틀렸다고 뜸), 아예 리턴시키는 방식으로 수정하였다.
// 좋은 해결 방법
int main() {
int N;
scanf("%d", &N);
int* arr = new int[N];
int* sorted = new int[N];
for (int i = 0; i < N; i++) {
scanf("%d", &arr[i]);
}
if (N == 1) { // N이 1일 때
printf("%d", arr[0]);
return 0;
}
merge_sort(arr, sorted, 0, N - 1);
for (int i = 0; i < N; i++) {
printf("%d\n", sorted[i]);
}
return 0;
}N = 1일 때는 전혀 생각하지도 못하고 그냥 다른 분들이 질문해둔 반례들만 입력해보기 바빴는데.. 이런 임계값에 해당하는 부분들도 주의깊게 보도록 해야겠다. 그리고 늦은 시간이였지만 자세히 알려주신 분 덕분에 많이 배워갈 수 있어서 감사하다. 나도 실력을 많이 키워서 지금의 나같은 초보자들에게 도움을 주고 싶다.
출처 : https://www.acmicpc.net/board/view/89750#comment-144258
3. 전체 코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
using namespace std;
void merge(int arr[], int sorted[], int left, int mid, int right) {
int i, j, k, l;
i = left; // 왼쪽 부분의 포인터 인덱스
j = mid + 1; // 오른쪽 부분의 포인터 인덱스
k = left; // 정렬된 배열에 넣을 인덱스
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) // 왼쪽 부분의 맨 앞쪽 값 <= 오른쪽 부분의 맨 앞쪽 값
sorted[k++] = arr[i++];
else
sorted[k++] = arr[j++];
}
if (i > mid)
for (l = j; l <= right; l++)
sorted[k++] = arr[l];
else
for (l = i; l <= mid; l++)
sorted[k++] = arr[l];
for (l = left; l <= right; l++)
arr[l] = sorted[l];
}
void merge_sort(int arr[], int sorted[], int left, int right) {
int mid;
if (left < right) {
mid = (left + right) / 2;
// 분할
merge_sort(arr, sorted, left, mid);
merge_sort(arr, sorted, mid + 1, right);
// 병합하며 정렬
merge(arr, sorted, left, mid, right);
}
}
int main() {
int N;
scanf("%d", &N);
int* arr = new int[N];
int* sorted = new int[N];
for (int i = 0; i < N; i++) {
scanf("%d", &arr[i]);
}
if (N == 1) {
printf("%d", arr[0]);
return 0;
}
merge_sort(arr, sorted, 0, N - 1);
for (int i = 0; i < N; i++) {
printf("%d\n", sorted[i]);
}
return 0;
}4. 제출 화면
