[백준/C언어] 2751번 - 수 정렬하기 2

백준 웹사이트 "2751번 - 수 정렬하기 2" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

2751번: 수 정렬하기 2

---

소스 코드

#include <stdio.h>

int * merge_sort(int * arr, int index, int len);
void merge(int * arr, int l_index, int r_index, int l_len, int r_len);

int main(void){
    int N;
    scanf("%d", &N);

    int arr[N];
    for(int i=0; i<N; i++){
        scanf("%d", &arr[i]);
    }

    // Merge Sort
    merge_sort(arr, 0, N);

    // 결과 출력
    for(int i=0; i<sizeof(arr)/sizeof(int); i++){
        printf("%d\n", arr[i]);
    }
}

int * merge_sort(int * arr, int index, int len){
    // Base Case
    if(len==1){
        return arr;
    }

    // Recursive Case
    // 1. arr을 반으로 나눈다
    int left = index;
    int right = index + len/2;
    int left_len = len/2;
    int right_len = len - len/2;

    // 2. 왼쪽, 오른쪽을 각각 merge_sort 한다
    merge_sort(arr, left, left_len);
    merge_sort(arr, right, right_len);

    // 3. 왼쪽, 오른쪽을 merge 한다
    merge(arr, left, right, left_len, right_len);
    return arr;
}

void merge(int * arr, int l_index, int r_index, int l_len, int r_len){
    // 1. 임시 배열 선언
    int temp[l_len+r_len];
    int count = 0;
    
    // 2. 왼쪽, 오른쪽의 가장 작은 수 비교
    int l_count = 0;
    int r_count = 0;
    while(1){
        int left = l_index + l_count;
        int right = r_index + r_count;
        if(arr[left] < arr[right]){
            temp[count] = arr[left];
            count++;
            l_count++;
        }
        else{
            temp[count] = arr[right];
            count++;
            r_count++;
        }

    // 3. 왼쪽이나 오른쪽의 끝에 도달하면 break
        if(l_count==l_len || r_count==r_len){
            break;
        }
    }

    // 4. 남은 요소 temp로 복사
    if(l_count==l_len){ // 오른쪽을 복사
        while(count<sizeof(temp)/sizeof(int)){
            temp[count] = arr[r_index+r_count];
            count++;
            r_count++;
        }
    }
    else{               // 왼쪽을 복사
        while(count<sizeof(temp)/sizeof(int)){
            temp[count] = arr[l_index+l_count];
            count++;
            l_count++;
        }
    }

    // 5. arr에 임시배열 복사
    for(int i=l_index; i<l_index+l_len+r_len; i++){
        arr[i] = temp[i-l_index];
    }
}

---

문제 풀이

  2750번에 이어 정렬 알고리즘을 짜는 문제로, 이번에는 시간 복잡도가 \(O(nlogn)\)인 정렬 알고리즘을 짜야 합니다. 시간 복잡도가 \(O(nlogn)\)인 정렬 알고리즘은 꽤나 효율적인 편에 속하며, 언어에 내장된 정렬 함수도 이 정도의 시간 복잡도를 보통 가집니다. 다만 코드를 짜는 것이 조금 까다로우며, 백준 웹사이트의 문제 설명에도 "어려운 알고리즘이므로 지금은 언어에 내장된 정렬 함수를 쓰는 것을 추천드립니다" 라고 쓰여있습니다. 그래도 한 번 도전해보고 싶은 분들은 계속 읽어주세요!

  이 문제에서 사용할 정렬 알고리즘은 Merge Sort (병합 정렬)입니다. Divide and conquer algorithm (분할 정복 알고리즘)의 일종으로, 알고리즘을 배우다보면 익숙해지는 개념입니다. 어떠한 큰 문제를 분할해서 해결한 후 결과를 합치자는 접근인데, 주로 재귀를 이용해 풀어낼 수 있습니다.

Merge Sort (출처: 위키피디아)

Merge Sort의 원리는 다음과 같습니다. 우선 수열을 가장 작은 단위 (한 숫자)로 나눈 후, 각 숫자를 바로 옆의 숫자와 비교하여 정렬된 숫자 2개짜리 수열들로 만듭니다. 다음으로는 숫자 2개짜리 수열들을 바로 옆의 수열들과 비교하여 정렬된 숫자 4개짜리 수열들로 만듭니다. 이러한 과정을 반복하여 모든 숫자를 정렬시킵니다. 작은 단위의 수열들을 계속 병합하여 정렬시키기 때문에 '병합 정렬'이라고 불립니다.

  소스 코드에서 Line 24의 'merge_sort'는 병합 정렬을 진행하는 재귀 함수입니다. 수열이 저장된 배열 'arr'과 두 정수 'index'와 'len'을 파라미터로 받습니다. 이때 index는 가장 왼쪽에 위치한 숫자의 인덱스를 의미하며, len은 부분 수열의 길이를 의미합니다. 수열이 입력되면, 수열을 절반으로 나눈 후, 왼쪽 수열과 오른쪽 수열을 merge_sort 시킨 후, 'merge' 함수로 양쪽을 다시 병합합니다. 여기서 'merge'는 왼쪽 수열과 오른쪽 수열이 입력되면, 두 수열의 병합을 진행하는 함수입니다 (Line 46).

  merge_sort와 merge가 어떻게 작동하는지 예제 입력 '5 4 3 2 1'로 알아봅시다. arr은 '5 4 3 2 1'이 저장된 길이 5의 배열이고, index는 0 (가장 왼쪽의 인덱스), len은 5입니다.

1. merge_sort(arr, 0, 5) 실행 (Line 16)
2. merge_sort(arr, 0, 2) 실행 (Line 38)
   2-1. merge_sort(arr, 0, 1) 실행 → arr 그대로 반환 (Base Case)
   2-2. merge_sort(arr, 1, 1) 실행 → arr 그대로 반환 (Base Case)
   2-3. merge(arr, 0, 1, 1, 1) 실행 → arr[0]=5, arr[1]=4를 정렬하여 (arr[0]=4, arr[1]=5)로 변경
3. merge_sort(arr, 2, 3) 실행 (Line 39)
   3-1. merge_sort(arr, 2, 1) 실행 → arr 그대로 반환 (Base Case)
   3-2. merge_sort(arr, 3, 2) 실행
        3-2-1. merge_sort(arr, 3, 1) 실행 → arr 그대로 반환 (Base Case)
        3-2-2. merge_sort(arr, 4, 1) 실행 → arr 그대로 반환 (Base Case)
        3-2-3. merge(arr, 3, 4, 1, 1) 실행 → arr[3]=2, arr[4]=1를 정렬하여 (arr[3]=1, arr[4]=2)로 변경
   3-3. merge(arr, 2, 3, 1, 2) 실행 → arr[2]=3, (arr[3]=1, arr[4]=2)를 정렬하여 (arr[2]=1, arr[3]=2, arr[4]=3)로 변경
4. merge(arr, 0, 2, 2, 3) 실행 (Line 42) → (arr[0]=4, arr[1]=5), (arr[2]=1, arr[3]=2, arr[4]=3)를 정렬하여
                                                                  (arr[0]=1, arr[1]=2, arr[2]=3, arr[3]=4, arr[4]=5)로 변경

꽤나 복잡하죠? 알고리즘의 핵심은 '단위 수열로 분할한 후, 정렬시키며 병합한다'입니다. 소스 코드에 대한 구체적인 설명은 소스 코드의 주석을 참고해주세요! 다시 말하지만 정렬 알고리즘을 처음 접하는 분께는 꽤나 어려운 코딩이므로, 처음에는 병합 정렬이 어떤 것인지만 이해해도 좋습니다ㅎㅎ.