[BOJ-24060][C++] 알고리즘 수업 - 병합 정렬 1

문제

오늘도 서준이는 병합 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 병합 정렬로 배열 A를 오름차순 정렬할 경우 배열 A에 K 번째 저장되는 수를 구해서 우리 서준이를 도와주자.

크기가 N인 배열에 대한 병합 정렬 의사 코드는 다음과 같다.

merge_sort(A[p..r]) { # A[p..r]을 오름차순 정렬한다.
    if (p < r) then {
        q <- ⌊(p + r) / 2⌋;       # q는 p, r의 중간 지점
        merge_sort(A, p, q);      # 전반부 정렬
        merge_sort(A, q + 1, r);  # 후반부 정렬
        merge(A, p, q, r);        # 병합
    }
}
 
# A[p..q]와 A[q+1..r]을 병합하여 A[p..r]을 오름차순 정렬된 상태로 만든다.
# A[p..q]와 A[q+1..r]은 이미 오름차순으로 정렬되어 있다.
merge(A[], p, q, r) {
    i <- p; j <- q + 1; t <- 1;
    while (i ≤ q and j ≤ r) {
        if (A[i] ≤ A[j])
        then tmp[t++] <- A[i++]; # tmp[t] <- A[i]; t++; i++;
        else tmp[t++] <- A[j++]; # tmp[t] <- A[j]; t++; j++;
    }
    while (i ≤ q)  # 왼쪽 배열 부분이 남은 경우
        tmp[t++] <- A[i++];
    while (j ≤ r)  # 오른쪽 배열 부분이 남은 경우
        tmp[t++] <- A[j++];
    i <- p; t <- 1;
    while (i ≤ r)  # 결과를 A[p..r]에 저장
        A[i++] <- tmp[t++]; 
}

 

입력

첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 108)가 주어진다.

다음 줄에 서로 다른 배열 A의 원소 $A_{1}, A_{2}, ..., A_{N}$이 주어진다. ($1 ≤ A_{i} ≤ 10^{9}$)

 

출력

배열 A에 K 번째 저장 되는 수를 출력한다. 저장 횟수가 K 보다 작으면 -1을 출력한다.

 

예제 입력 1

5 7
4 5 1 3 2

 

예제 출력 1 

3

4 5 1 3 2 -> 4 5 1 3 2 -> 4 5 1 3 2 -> 1 5 1 3 2 -> 1 4 1 3 2 -> 1 4 5 3 2 -> 1 4 5 2 2 -> 1 4 5 2 3 -> 1 4 5 2 3 -> 1 2 5 2 3 -> 1 2 3 2 3 -> 1 2 3 4 3 -> 1 2 3 4 5. 총 12회 저장이 발생하고 일곱 번째 저장되는 수는 3이다.

 

예제 입력 2 

5 13
4 5 1 3 2

 

예제 출력 2 

-1

저장 횟수 12가 K 보다 작으므로 -1을 출력한다.

 

 

알고리즘 분류

• 구현
• 정렬
• 재귀

 

문제 출처

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

24060번: 알고리즘 수업 - 병합 정렬 1

 

---

 

문제 해결 방법

• 벡터(vector)를 이용하여 문제를 해결하려고 하였으나, 시간 초과 오류가 떴다. 그래서 1차원 배열과 동적 할당을 이용하여 문제를 해결하였다.
• merge() 함수 안에 tmp 1차원 배열을 동적 할당하였으나, 메모리 초과 오류가 떴다. 그래서 main() 함수에서 nums 배열에 이어 tmp 배열을 동적 할당시켜 주었다.
  • 재귀로 인해 merge() 함수가 여러번 호출됨과 동시에 동적 할당이 발생하여 메모리 초과 오류가 나오는 듯 했다.
• merge() 함수의 마지막 while 문 부분에서 배열 ary에 변수가 최종적으로 저장된다. while 문이 한 번씩 반복할 때 마다 cnt 값을 하나씩 증가시켜주고,  입력 받은 K와 cnt 값이 같을 경우(cnt == K) 배열 ary에 저장된 요소(ary[i - 1])가 출력되도록 하였다.
  • 그렇지 않을 경우 -1이 출력되도록 하였다.

 

코드

			
			
			
		
#include <iostream>
using namespace std;
 
int A, K, num, cnt, *nums, *tmp, answer = -1;
 
// A[p..q]와 A[q+1..r]을 병합하여 A[p..r]을 오름차순 정렬된 상태로 만든다.
// A[p..q]와 A[q+1..r]은 이미 오름차순으로 정렬되어 있다.
void merge(int *ary, int p, int q, int r) {
    int i, j, t;
 
    i = p;
    j = q + 1;
    t = 1;
 
    while (i <= q && j <= r) {
        if (ary[i] <= ary[j]) {
            tmp[t++] = ary[i++];    // tmp[t] = A[i]; t++; i++;
        }
        else {
            tmp[t++] = ary[j++];    // tmp[t] = A[j]; t++; j++;
        }
    }
    while (i <= q) {    // 왼쪽 배열 부분이 남은 경우
        tmp[t++] = ary[i++];
    }
    while (j <= r) {
        tmp[t++] = ary[j++];    // 오른쪽 배열 부분이 남은 경우
    }
 
    i = p;
    t = 1;
 
    while (i <= r) {    // 결과를 A[p..r]에 저장
        ary[i++] = tmp[t++];
        cnt++;
        if (cnt == K) {
            answer = ary[i - 1];
            break;
        }
    }
}
 
void merge_sort(int *ary, int p, int r) {
    if (p < r) {
        int q = (p + r) / 2;     // q는 p, r의 중간 지점 (내림)
        merge_sort(ary, p, q);    // 전반부 정렬
        merge_sort(ary, q + 1, r);    // 후반부 정렬
        merge(ary, p, q, r);    // 병합
        
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> A >> K;
 
    nums = new int[A];    // 벡터를 이용하여 문제를 풀 경우 시간 초과 오류 발생
    tmp = new int[A];    // merge() 함수 내부에서 동적 할당을 할 경우, '메모리 초과' 오류 발생
 
    for (int i = 0; i < A; i++) {
        cin >> num;
        nums[i] = num;
    }
    
    merge_sort(nums, 0, A - 1);
 
    cout << answer << '\n';
 
    delete[] nums;
    delete[] tmp;
 
    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [재귀]
• 실버IV

 

병합/합병 정렬(Merge Sort)

• 안정된 정렬(Stable Sort) 방법에 속하며, 분할 정복(Divide and Conquer) 알고리즘의 하나이다.
• 존 폰 노이만(John von Neumann)이 제안한 방법

 

작동 과정

• 다음과 같은 과정에 의해 병합 정렬이 수행된다.
  • 분할(Divide) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
  • 정복(Conquer)  : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 재귀 호출을 이용하여 다시 분할 정복 방법을 적용한다.
  • 결합(Combine) : 정렬된 부분 배열들을 하나의 배열에 병합한다.

(i) 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
(ii) 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
(iii) 각 부분 리스트를 재귀적으로 병합 정렬을 이용해 정렬한다.
(iv) 두 부분 리스트를 다시 하나의 정렬된 리스트로 병합한다.

 

병합 정렬의 작동 원리

 

특징

• 병합 정렬을 위해서는 추가적인 리스트가 필요하다.
• 각 부분 배열을 정렬할 때도 병합 정렬을 재귀적으로 호출하여 적용한다.
• 병합 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 병합하는 단계이다.

 

장점

• 데이터의 분포에 영향을 덜 받아 안정적인 정렬을 수행할 수 있다.
  • 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다. ($O(n \log_{2} n)$)
• 레코드를 연결 리스트(Linked List)로 구성하면, 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다.
  • 제자리 정렬(In-Place Sorting)로 구현할 수 있다.
  • 크기가 큰 레코드를 정렬할 경우, 연결 리스트를 사용할 경우 병합 정렬은 퀵 정렬을 포함한 어떤 정렬 방법보다도 효과적이다.

 

단점

• 제자리 정렬(In-Place Sorting)이 아니다. 레코드를 배열(Array)로 구성하면, 임시 배열이 필요하다.
• 레코드들의 크기가 큰 경우, 이동 횟수가 많으므로 시간이 크게 낭비될 수 있다.

 

알고리즘

			
			
			
		
int tmp[MAX_SIZE];    // 추가적인 공간 필요
 
void merge(int list[], int left, int mid, int right) {
    int i, j, k, l;
    
    i = left;       // 정렬된 왼쪽 리스트에 대한 인덱스
    j = mid + 1;    // 정렬된 오른쪽 리스트에 대한 인덱스
    k = left;       // 정렬된 리스트에 대한 인덱스
    
    // 분할 정렬된 리스트의 병합
    while (i <= mid && j <= right) {
        if (list[i] <= list[j]) {
            tmp[k++] = list[i++];
        }
        else {
            tmp[k++] = list[j++];
        }
    }
    
    // 남아 있는 값들을 복사
    if (i > mid) {
        for (int l = j; l <= right; l++) {
            tmp[k++] = list[l];
        }
    }
    else {
        for (int l = i; l <= mid; l++) {
            tmp[k++] = list[l];
        }
    }
    
    // 임시 배열의 리스트를 원래 배열로 다시 복사
    for (int l = left; l <= right; l++) {
        list[l] = tmp[l];
    }
}
 
void merge_sort(int list[], int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;    // 중간 위치를 계산하여 리스트를 균등 분할 - 분할(Division)
        merge_sort(list, left, mid);     // 앞쪽 부분 리스트 정렬 - 정복(Conquer)
        merge_sort(list, mid + 1, right);     // 뒤쪽 부분 리스트 정렬 - 정복(Conquer)
        merge(list, left, mid, right);    // 정렬된 2개의 부분 배열 병합 - 결합(Combine)
    }
}

 

사용 예

			
			
			
		
#include <iostream>
using namespace std;
 
#define MAX_SIZE 8
 
int tmp[MAX_SIZE];    // 추가적인 공간 필요
 
void merge(int list[], int left, int mid, int right) {
    int i, j, k, l;
    
    i = left;       // 정렬된 왼쪽 리스트에 대한 인덱스
    j = mid + 1;    // 정렬된 오른쪽 리스트에 대한 인덱스
    k = left;       // 정렬된 리스트에 대한 인덱스
    
    // 분할 정렬된 리스트의 병합
    while (i <= mid && j <= right) {
        if (list[i] <= list[j]) {
            tmp[k++] = list[i++];
        }
        else {
            tmp[k++] = list[j++];
        }
    }
    
    // 남아 있는 값들을 복사
    if (i > mid) {
        for (int l = j; l <= right; l++) {
            tmp[k++] = list[l];
        }
    }
    else {
        for (int l = i; l <= mid; l++) {
            tmp[k++] = list[l];
        }
    }
    
    // 임시 배열의 리스트를 원래 배열로 다시 복사
    for (int l = left; l <= right; l++) {
        list[l] = tmp[l];
    }
}
 
void merge_sort(int list[], int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;    // 중간 위치를 계산하여 리스트를 균등 분할 - 분할(Division)
        merge_sort(list, left, mid);     // 앞쪽 부분 리스트 정렬 - 정복(Conquer)
        merge_sort(list, mid + 1, right);     // 뒤쪽 부분 리스트 정렬 - 정복(Conquer)
        merge(list, left, mid, right);    // 정렬된 2개의 부분 배열 병합 - 결합(Combine)
    }
}
 
 
int main() {
    int i, list[MAX_SIZE] = { 38, 22, 11, 40, 93, 77, 13, 95 };
    
    cout << "정렬 전 : ";
    for (int i = 0; i < MAX_SIZE; i++) {
        cout << list[i] << " ";
    }
    
    cout << endl;
    
    cout << "정렬 후 : ";
    merge_sort(list, 0, MAX_SIZE - 1);
    
    for (int i = 0; i < MAX_SIZE; i++) {
        cout << list[i] << " ";
    }
    
    return 0;
}

			
			
			
		
정렬 전 : 38 22 11 40 93 77 13 95 
정렬 후 : 11 13 22 38 40 77 93 95

 

참고 사이트

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