[백준] 2751번 : 수 정렬하기 2 | C++

1. 문제 상세

 

https://www.acmicpc.net/problem/2751

 

 

 

2. 문제 접근

 

주어진 수들을 정렬하기 위해 합병 정렬 알고리즘을 사용해보자.

이번 문제에서 유의할 점은 시간 제한이다.

 

이번 문제에서 정렬 할 수들의 최대 갯수는 1,000,000개이다.

즉 시간복잡도가 O(N²)인 정렬 알고리즘을 사용한다면 제한시간을 초과하게 된다.

지금까지 알아본 버블, 선택, 삽입 정렬은 시간복잡도가 O(N²)이기 때문에 사용할 수 없다.

퀵 정렬을 사용해볼까 싶었지만 퀵 정렬에서도 최악의 경우에는 시간복잡도가 O(N²)이기 때문에

이번에는 합병 정렬을 사용해보자.

 

■ 합병 정렬

합병 정렬 알고리즘은 주어진 원소들을 분할, 정복, 결합 과정을 통해 정렬해가는 알고리즘이다.

분할 과정에서는 배열을 중간 값을 기준으로 2개의 부분배열로 나눈다.

정복 과정에서는 배열의 값을 정렬하는데, 부분 배열의 크기가 충분히 작지 않다면 순환 호출로 부분 배열을 더

작게 나눈다.

결합 과정에서는 부분 배열의 값들을 정렬하며 하나의 배열로 합쳐간다.

 

코드 상에서 정렬은 결합 과정에서 실행되기 때문에

정복 과정은 부분 배열이 충분히 작은지 판단하는 과정이라고 볼 수 있다.

 

배열을 부분배열로 나누며 부분 배열의 크기가 0 또는 1이 될 때 까지 나눈다.나누고 나면 부분 배열의 원소를 비교, 작은 값을 새로운 배열에 먼저 넣어가며 부분 배열을 정렬하며 결합한다.부분 배열을 모두 결합하면 정렬이 완료된다.

 

출처 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

 

 

 

아래는 합병 정렬의 결합 과정이다.

임시 배열 sorted 에 부분 배열의 값을 앞에서부터 비교해가며 작은 순서대로 넣고,

모든 값을 넣고 나면 기존 배열 list 에 값을 복사해 넣는다.

출처 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

 

 

 

합병 정렬의 시간복잡도를 확인해보자.

먼저 비교 횟수를 확인하기 위해 합병 횟수, 즉 순환 호출의 깊이를 확인해보자.

원소의 개수가 n 이 2의 거듭제곱이라고 가정할 때, n = 2³ 인 경우는 2³ - 2² - 2¹ - 2⁰ 으로 깊이가 3이 된다.

이를 보면 n = 2^k 라고 볼 때 k=log₂n 이므로 합병 횟수는 log₂n 이 된다.

 

각 합병 단계에서 비교 횟수는 최대 n 번 이므로, 둘을 곱하여 비교 횟수는 nlog₂n 이 된다.

 

이동 횟수를 보면 합병 횟수는 동일하게 log₂n, 합병 단계에서 이동 횟수는 임시 배열에 복사, 정렬하여 원래 배열로 복사 하는

두 번의 이동을 거치기 때문에 2n 번, 이를 곱하여 2nlog₂n 번이 된다.

 

결과적으로 합병 정렬의 시간복잡도는 O(nlog₂n)이다.

 

아래 사진을 통해 합병 정렬의 시간복잡도를 다른 정렬 알고리즘의 시간복잡도와 비교해보자.

구현이나 정렬 과정은 복잡하지만 더욱 효율적인 알고리즘인것을 알 수 있다.

출처 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

 

 

문제풀이를 통해 합병 정렬을 구현해보자.

 

 

 

3. 문제 풀이

 

#include <iostream>
using namespace std;

int sorted[1000000], list[1000000];

void merge(int list[], int left, int mid, int right) {
    int i = left, j = mid + 1, k = left, l;

    while (i <= mid && j <= right) {
        if (list[i] <= list[j]) sorted[k++] = list[i++];
        else sorted[k++] = list[j++];
    }

    if (i > mid) {
        for (l = j; l <= right; l++) {
            sorted[k++] = list[l];
        }
    }
    else {
        for (l = i; l <= mid; l++) {
            sorted[k++] = list[l];
        }
    }

    for (l = left; l <= right; l++) {
        list[l] = sorted[l];
    }
}

void merge_sort(int list[], int left, int right) {
    int mid;
    if (left < right) {
        mid = (left + right) / 2;
        merge_sort(list, left, mid);
        merge_sort(list, mid + 1, right);
        merge(list, left, mid, right);
    }
}

int main() {
    int n;

    cin >> n;

    for (int i = 0; i < n; i++) cin >> list[i];

    merge_sort(list, 0, n - 1);

    for (int i = 0; i < n; i++) cout << list[i] << '\n';
}

 

크기가 10만인 정수형 배열 sorted 와 list 를 전역변수로 선언한다.

/* 함수 내부에서 이 정도로 큰 크기의 배열을 선언하고 많이 사용하면

함수를 실행에 사용되는 스택의 크기를 벗어나는 경우가 많으므로 주의하자. */

 

함수 merge 를 선언, 매개변수로 배열(list)과 정수 세 개(left, mid, right)를 받는다.

/* 정렬, 결합 과정의 함수 선언, 매개변수로 배열, 배열의 앞(부분 배열1의 맨 앞 인덱스),

중간(부분 배열 1의 마지막 인덱스, 여기에 +1 을 하면 부분 배열2의 맨 앞 인덱스),

마지막 인덱스(부분 배열 2의 마지막 인덱스)를 전달받는다. */

정수 i. j. k. l 을 선언하고 각각 i 는 left, j 는 mid + 1, k 는 left 로 초기화 한다.

// 부분 배열로 나눈 인덱스를 참조용으로 복사한다.

 

while문으로 i 가 mid 보다 작거나 같고, j 가 right 보다 작거나 같을 때 반복한다.

// 각 부분 배열에서 한 배열의 원소가 남지 않을 때 까지 반복한다.

if문으로 list 의 i 번 인덱스 값이 j 번 인덱스의 값보다 작거나 같으면,

sorted 의 k 번 인덱스에 list 의 i 번 인덱스 값을 저장하고 k 와 i 에 1씩 더한다.

아닌 경우 sorted 의 k 번 인덱스에 list 의 j 번 인덱스 값을 저장하고 k 와 j 에 1씩 더한다.

/* 조건문을 통해 부분 배열의 앞부터 값을 비교, 더 작은 값을 임시 배열인 sorted 에 복사한다.

복사 후에 참조용 인덱스를 증가시킨다. */

반복을 빠져나오면 if문으로 i 가 mid 보다 큰지 확인한다.

크다면 l 이 j 부터 right 보다 작거나 같을 때 1씩 더하며 반복하도록 한다.

반복에서는 sorted 의 k 번 인덱스에 list 의 l 번 인덱스 값을 저장하고 k 를 1증가시킨다.

/* i 가 크다면 부분 배열1의 원소가 모두 정렬하며 결합되었다는 뜻이므로

for문으로 j(부분 배열2 의 앞 인덱스)를 참조하여 부분 배열2의 남은

원소들을 모두 sorted 배열에 넣어준다. */ 

아닌 경우 l 이 i 부터 mid 보다 작거나 같을 때 1씩 더하며 반복하고,

반복에서는 sorted 의 k 번 인덱스에 list 의 l 번 인덱스 값을 저장하고 k 를 1증가시킨다.

/* 위의 조건이 아닐 때는 j 가 커져서, 즉 부분 배열2의 원소를 모두 결합한 경우일수도

있기 때문에 for문으로 i(부분 배열1 의 앞 인덱스)를 참조하여 부분 배열1의 남은

원소들을 모두 sorted 배열에 넣어준다. */ 

모든 반복이 끝나면 for문으로 l 이 left 부터 right 보다 작거나 같을 때, 1씩 더하며 반복,

반복에서는 list 의 l 번 인덱스에 sorted 의 l 번 인덱스 값을 저장한다.

// 부분 배열들을 결합한 임시 배열의 값을 원본 배열로 복사한다.

 

함수 merge_sort 를 선언, 매개변수로 배열(list)과 정수 두 개(left, right)를 받는다.

/* 분할, 정복 과정의 함수를 선언, 매개변수로 배열, 배열의 앞(부분 배열 1의 맨 앞 인덱스가 될 값) 

배열의 맨 뒤(배열의 끝, 이 값과 맨 앞의 값을 더해 2로 나누면 중간 인덱스, 즉 부분 배열 1의 맨 뒤 인덱스가 된다.) */

정수형 변수 mid 를 선언. // 중간값을 저장할 변수 선언.

if문으로 left 가 right 보다 작을 때, // 배열의 크기가 1이상인 경우.

mid 에 left + right 를 2로 나눈 값을 저장한다. // 중간값을 구해 mid 에 저장.

merge_sort 함수에 list, left, mid 를 전달하여 호출. // 부분 배열(앞쪽)로 분할 후 다시 분할 함수로 전달.

merge_sort 함수에 list, mid + 1, right 를 전달하여 호출. // 부분 배열(뒤쪽)로 분할 후 다시 분할 함수로 전달.

merge 함수에 list, left, mid, right 를 전달하여 호출.

/* 위에서 실행 한 merge_sort 함수를 순환 호출 하였기 때문에 배열이 제일 작은 부분 배열까지

분할되며 순환 호출되고. 그 후에는 제일 작은 부분 배열부터 결합 과정을 거쳐 배열의 값을 정렬시킨다. */

 

main 함수에서는 정수 n 을 선언 // 입력받을 수의 개수를 저장할 n 선언.

cin 으로 정수(정수의 개수)를 입력받아 n 에 저장.

 

for문으로 i 가 0 부터 n 보다 작을 때 1씩 더하며 반복,

cin 으로 list 의 i 번 인덱스에 정수를 입력받아 저장. // 배열의 값을 입력받는다.

 

merge_sort 함수에 list, 0, n - 1 을 전달하여 호출.

// list 배열과 배열의 맨 앞 인덱스 0, 맨 뒤 인덱스인 n - 1을 전달한다.

 

for문으로 i 가 0 부터 n 보다 작을 때 1씩 더하며 반복,

cout 으로 list 의 i 번 인덱스의 값과 개행문자를 출력한다.

/* 함수 호출이 끝나고 정렬이 완료되면 정렬된 배열을 출력한다.

여기서 주의할 점이 있었다, 개행문자가 아닌 endl 을 사용하여 개행하는 경우

endl 은 개행외에도 버퍼로 flush 하는 동작이 있어서 출력이 많을 때 시간이 많이 걸린다.

이 때문에 정렬을 잘 구현했음에도 문제 시간 초과가 발생하였다.

개행문자를 직접 출력하도록 하자. */ 

 

 

*참고*

예시 배열 { 21, 10, 12, 20, 25, 13, 15, 22 } 가 주어졌을 때 코드의 실행 과정

출처 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

 

 

 

4. 성능 확인

 

 

 

 

5. 마무리

 

이미지 및 참고 글 출처 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

 

여러모로 생각해야 할 조건이 많은 문제였다.

시간 초과를 해결하기 위해 이를 충족하는 정렬 알고리즘의 선택,

이를 구현하는 과정에서 함수 스택의 크기를 유의해 배열을 전역 변수로 선언,

개행 시 flush 동작을 하는 endl 대신 개행문자 '\n' 을 출력하기 등등..