합병정렬 (MergeSort)

합병정렬은 대표적인 분할 정복 알고리즘이다. start==end가 되기 직전까지 분할을 계속 하다가 즉 start,start+1,// end-1,end 와 같이 분할이 단일범위까지 진행되다가 다시 이 단일 범위서부터 분할했던 경로 그대로 역순으로 되돌아가며 정복을 하는 알고리즘이다.  

 

분할 정복을 하는 순서는 항상 다음을 따른다.

mid=(start+end)/2를 기준으로 start~mid 부분인 좌측 부분의 분할이 먼저 이루어지고 그다음 mid+1~end까지 분할이 이루어진 후 합병이 시작된다.

 

즉 큰 틀로보면 왼쪽분할 - 오른쪽분할 - 정복 순서를 원자단위에서부터 차례차례 수행해 나가는 구조이다.

그리고 이를 그림으로 그려보면 다음과 같다.

원자단위로 왼쪽부터 분할 해 나간 후 오른쪽부분을 분할하고 정복을 하게되고 이렇게 뭉쳐진 2크기의 묶음을 기준으로 하면 아직 오른쪽은 분할이 되지 않은 상태이므로 오른쪽도 2크기의 묶음이 되도록 분할정복을 거치고 이 2, 2 덩어리가 왼쪽, 오른쪽 분할이 된 상태이니 정복을 하게되면 정렬된 4개크기의 덩어리가 된다. 마찬가지로 오른편의 4개도 다시 왼쪽부터 분할과정 그리고 오른쪽 분할 , 정복을 순서대로 거치면 위 그림과 같이 정렬이 된다.

 

이 분할정복을 코드로 출력해보면 다음과 같이 이루어진다.

초기 배열이 8 7 6 5 4 3 2 1 이고 이을 오름차순으로 정렬하는 과정은 다음과 같다. 원래 합병정렬 소스코드는 달리기문제때문에 변형이 조금 돼 있어서 출력화면만 띄웠음.

앞서 설명한 과정이나 그림과 동일한 방식으로 분할정복이 되고 있다는 것을 확인 할 수있다.

정렬 수도 코드

정복 

 

이 분할 정복을 활용하여 문제를 풀어보자.

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

2517번: 달리기

달리기 문제인데 

처음 n개만큼 숫자가 주어지고 각 숫자의 크기만큼 실력이라고 할 수 있다.

예를들어 2 5 4 3 1 7 이라고 주어졌다고 가정하자. 이 숫자들은 자신의 번호보다 작은 번호들을 앞지를 수 있다. 그래서 각 숫자마다 할 수 있는 최고의 등수를 출력하는 문제이고 위의 예에서는 1 1 2(4는 5를 앞지를 수 없으므로) 3 5 1 이 출력돼야 한다. 

여기서 1부터 n까지  자신의 앞사람들을 모두 확인하는 일반적인 알고리즘이라면 시간복잡도가 1+2+3+4+...+n즉 O(시그마N)=O(N^2)이 나와 N의 범위가 50만이여서 1250억 가량의 탐색을 하게되고 이는 매우매우 오래 걸리므로 시간초과가 발생하게 된다. 그래서 N(logN)인 합병정렬을 적용하면 일단 탐색 횟수는 1000만 가량으로 매우 줄게 된다.

그리고 왜 합병정렬이냐면 먼저 구조체 배열을 만들어 value, 원래 위치, 카운트 변수(제칠 수 있는 횟수)를 생성하여 합병시 왼쪽으로 분할돼 있는 point들이 그대로 왼쪽으로 갈 경우 이 뜻은 오른쪽에 있는 point보다 작아서 왼쪽에 그대로 삽입되는 것이므로 오른쪽에 있는 point들이 재칠 수 있는 point가 그만큼 증가한다는 뜻이된다. 그래서 이러한 경우 카운트 변수를 관리하여 오른쪽으로 분할이 돼 있던 point들에 값을 부여하면 문제를 해결할 수 있다. 그래서 이러한 원리를 적용하여 기존 합병정렬 코드를 조금 변형 시켜서 문제를 해결하였다.

 

소스코드