[실전 알고리즘] 0x08강 - 정렬_구버전

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

현재 보고있는 강의는 구버전입니다. 내용에는 문제가 없으나 리뉴얼 중이니 이 게시글을 참고해주세요.

 

리뉴얼한 버전은 [실전 알고리즘] 0x0E강 - 정렬 I, [실전 알고리즘] 0x0F강 - 정렬 II에서 확인할 수 있습니다. 리뉴얼 버전으로 보시는 것을 추천드립니다.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

 

 

 

 

이번 시간에는 정렬을 해보도록 하겠습니다. 분량이 어마어마하니 미리 마음의 준비를 하고 오세요.

 

하는 김에 다 해버리자 싶어서 Merge Sort, Quick Sort, Counting Sort, Radix Sort를 모두 다룹니다!

 

시작은 무난합니다. 책꽂이에 꽂혀있는 책을 크기 순으로 정렬하고 싶으면 어떻게 하나요? 프로그래밍 문제라고 생각하지 말고 눈앞에 책꽂이가 있다고 생각하고 고민해보세요.

 

거의 대부분의 사람들은 가장 큰 것부터 차례로 오른쪽에 꽂거나, 가장 작은 것 부터 차례로 왼쪽에 꽂는 방법을 사용할 것입니다. 혹시 이 두개 말고 다른 방법으로 하신 분 있으신가요?

 

저는 가장 큰 것부터 찾아서 오른쪽에 꽂아보겠습니다.

 

이제 이 과정을 배열에서 수행해보려고 합니다. 그 전에 시간복잡도가 얼마일지 맞춰봅시다. $K$개의 원소 중에서 가장 큰 원소를 찾는데는 $O(K)$가 걸립니다. 그러면 아까의 정렬 과정에서 맨 처음엔 $N$개의 원소 중에서 제일 큰 원소를 찾고, 두 번째로 $N-1$개의 원소 중에서 제일 큰 원소를 찾고, … 마지막으로는 1개의 원소 중에서 제일 큰 원소를 찾아야 하므로 총 시간복잡도는 $N+(N-1)+(N-2)+…+2+1$ = $N(N-1)/2 = O(N^2)$ 입니다.

 

사실 앞에서부터 인접한 두 원소를 보며 앞의 원소가 뒤의 원소보다 클 경우 자리를 변경하는 것을 반복하면 자연스럽게 제일 큰 것부터 오른쪽에 쌓입니다.

 

코드로 이렇게 간단하게 나타낼 수 있습니다. 이러한 정렬 방법을 Bubble Sort라고 합니다.

 

$O(N^2)$에 동작하는 정렬은 Bubble Sort 이외에도 Insertion Sort, Selection Sort가 존재합니다. 학부 수업 시간에는 보통 3개의 정렬이 각각 어떤 것인지 배우고 넘어가지만 Bubble Sort만 알고 있어도 코딩테스트에서는 아무 문제 없습니다. 심지어 STL을 쓸 수 있는 테스트라면 아예 Sort를 짤 일이 없습니다.

 

면접에서도 Bubble/Insertion/Selection Sort를 묻지 않는다고 100% 장담할 수는 없지만 99.9999% 정도로 확신합니다. 당장 저도 3개의 Sort를 구분 못합니다. 중요한 내용도 아니구요.

 

STL을 쓸 수 없고 $N$이 작아 $O(N^2)$으로 짜도 문제가 없을 때에 한해 Bubble Sort가 필요합니다. 만약 $N$이 클 땐 더 빠른 정렬 알고리즘을 사용해야 합니다.

 

$O(N^2)$보다 더 빠르게 동작하는 첫 번째 알고리즘인 Merge Sort입니다. Merge Sort는 재귀적으로 수열을 나눠 정렬한 후 합치는 정렬법으로 $O(NlgN)$에 동작합니다. Merge Sort는 분할 정복(Divide and Conquer) 알고리즘의 대표적인 예시입니다. 참고로 분할 정복 알고리즘은 이번 실전 알고리즘 강의에서 다루지 않을 예정입니다.

 

Merge Sort를 설명하기 전에 우선 길이가 $N$, $M$인 두 정렬된 리스트를 합쳐 $O(N+M)$에 길이 $N+M$의 정렬된 리스트를 만들어봅시다. 어떻게 할 수 있을까요?

 

우선 두 리스트를 합쳤을 때 제일 앞에 와야 하는 원소, 즉 리스트 A와 B를 통틀어서 가장 작은 원소가 무엇일지 어떻게 알 수 있을까요?

 

상식적으로 생각했을 때 그 원소는 A에서 가장 작은 원소이거나 B에서 가장 작은 원소일 것입니다. 그러니 -9와 -7을 비교해보면 -9가 더 작으니 -9가 제일 앞에 온다는 것을 알 수 있습니다.

 

그 다음 원소는 무엇인지 어떻게 알 수 있을까요? 그 다음 원소는 -9를 제외한 나머지들 중에서 가장 작은 수입니다. 앞에서 한 것과 비슷한 논리로 생각해보면 그 다음 원소는 A에서 -9를 제외하고 가장 작은 원소이거나 B에서 가장 작은 원소일 것입니다.

 

1과 -7중에 -7이 더 작으니 -7이 그 다음 원소임을 알 수 있습니다.

 

마찬가지 논리로 계속 진행합니다.

 

 

 

 

 

리스트 A의 모든 원소를 다 사용했으므로 남은 B의 원소를 모두 넣으면 됩니다.

 

정렬이 완료됐습니다.

 

예시 코드입니다. 조금 복잡하긴 하네요. 아까 리스트 A, B와 합쳐진 리스트에 있던 화살표가 각각 idx1, idx2, idx0이라고 생각하면 됩니다.

 

BOJ 11728번 : 배열 합치기 문제를 통해 코드가 잘 동작하는지 검증해볼 수 있습니다.(정답 코드)

 

두 정렬된 리스트를 합치는 과정만 이해하고 나면 Merge Sort는 어렵지 않습니다. Merge Sort는

1. 주어진 리스트를 2개로 나눈다.
2. 나눈 리스트 2개를 정렬한다.
3. 정렬된 두 리스트를 합친다.

가 다입니다!

 

그런데 나눈 리스트 2개를 정렬하기 위해서는 재귀적으로 또 다시 각각을 2개로 나눠야합니다. 단 길이가 2 이하일 경우에는 base condition으로 생각해 직접 처리합시다. 그러므로 엄밀하게는 이런 식으로 동작합니다.

 

이제 Merge Sort의 시간복잡도를 분석해봅시다. 약간의 수학적 관찰력이 필요하기 때문에 잘 이해가 안가면 그냥 넘어가도 상관없습니다. 리스트를 쪼개는 과정에서는 최대 $O(N)$번의 재귀호출이 발생하기 때문에 시간복잡도에 큰 영향을 주지 않습니다. 중요한 것은 리스트를 합쳐나가는데 걸리는 시간입니다.

 

우선 길이 2짜리 리스트 $N/2$개를 각각 정렬하는데 필요한 시간복잡도는 $O(N)$입니다.

 

그 다음 길이 2짜리 리스트 $N/2$개를 둘씩 짝지어 합치는데 필요한 시간복잡도는 전체 리스트의 길이의 합인 $O(N)$입니다. 앞에서 다뤘듯 길이가 $N$, $M$인 두 정렬된 리스트를 합치는데 필요한 시간복잡도가 $O(N+M)$이었기 때문에 전체 리스트의 길이의 합이 어디서 나왔는지 알 수 있을 것입니다.

 

그 다음으로 길이 4짜리 리스트 $N/4$개를 둘씩 짝지어 합치는데 필요한 시간복잡도는 마찬가지로 전체 리스트의 길이의 합인 $O(N)$입니다.

 

이런식으로 내려가다보면 $N = 2^k$일 때 최대 $k$단계에 걸쳐 나눠지고 합치는 $k$개의 각 과정에서 $N$번씩 연산을 해야 리스트를 합칠 수 있으므로 시간복잡도는 $O(Nk)$ = $O(NlgN)$입니다.

 

Merge Sort의 예시 코드를 참고해보세요. Merge Sort는 $N$만큼의 추가적인 메모리를 필요로 하지만 $O(NlgN)$에 정렬할 수 있기 때문에 STL을 지원하지 않는 시험에서 10,000개 이상의 원소를 정렬해야 하면 Merge Sort를 사용하는 것이 좋습니다. 단, 특정 조건을 만족하면 뒤에 소개할 Counting Sort가 더 빠르고 코딩하기 쉬울 수 있습니다.

 

Merge Sort는 같은 key를 가진 원소들이 Sorting을 한 후에도 순서가 달라지지 않는 Stable Sort입니다.

 

다음으로 Quick Sort를 다뤄보겠습니다. Quick Sort는 기준 원소를 하나 잡아 수열을 좌우로 나눈 후에 각각을 따로 정렬하는 정렬법입니다. 평균적으로 $O(NlgN)$, 최악의 경우 $O(N^2)$에 동작합니다. Merge Sort와 비교할 때 Quick Sort는 추가적인 메모리를 필요로 하지 않고 평균적인 속도 또한 Merge Sort보다 빠릅니다. 그러나 같은 key를 가진 원소들이 Sorting을 한 후 순서가 달라질 수 있는 Unstable Sort이고 무엇보다 최악의 경우 $O(N^2)$이기 때문에 코딩테스트에서는 Quick Sort를 사용하면 안됩니다.

 

안하고 갈 수가 없는 중요한 내용이라 Quick Sort를 설명하고 가긴 하지만, 코딩테스트만을 위해서 급하게 공부를 하고 있는 상황이라면 일단 Quick Sort를 건너뛰고 기술면접 대비를 할 때 다시 살펴보세요.

 

Quick Sort에서는 pivot을 기준으로 수열을 나눈 방법만 이해하면 그 이후는 Merge Sort와 같이 재귀적으로 처리할 수 있습니다.

 

일단 주어진 배열에서 임의로 pivot을 하나 잡아야합니다. 편의상 제일 왼쪽에 위치한 6을 pivot으로 잡겠습니다. 만약 12와 같은 다른 값을 잡고 싶으면 그냥 6과 자리를 바꿔버리면 마찬가지로 pivot이 제일 왼쪽에 위치한다고 생각해버릴 수 있는 상황임을 알 수 있습니다.

 

우리의 목적은 배열 내에서 pivot을 올바른 자리에 넣고 pivot의 왼쪽은 pivot보다 작은 원소가, 오른쪽에는 pivot보다 큰 원소가 오게끔 하는 것입니다.

 

Pivot을 제외한 나머지 배열의 제일 왼쪽과 오른쪽에 포인터를 2개 둡니다. 왼쪽의 포인터는 오른쪽으로 움직이고 오른쪽의 포인터는 왼쪽으로 움직입니다.

 

왼쪽의 포인터를 $l$, 오른쪽의 포인터를 $r$이라고 하겠습니다.

 

$l$은 pivot보다 큰 값을 찾을 때 까지 오른쪽으로 계속 움직일 것입니다.(단 $l$이 $r$보다 더 오른쪽에 위치하게 되면 그 즉시 멈춥니다.) $r$은 pivot보다 작은 값을 찾을 때 까지 왼쪽으로 움직일 것입니다.(단 $r$이 $l$보다 더 왼쪽에 위치하게 되면 그 즉시 멈춥니다.)

 

$l$을 6보다 큰 값을 찾을 때 까지 오른쪽으로 움직이다가 12를 찾았습니다.

 

$r$은 6보다 작은 값을 찾을 때 까지 왼쪽으로 움직이려고 했는데 자기 자신이 6보다 작으므로 움직이지 않습니다.

 

현재 $l$이 가리키고 있는 12는 원래 pivot의 오른쪽에 있어야하고 $r$이 가리키고 있는 -7은 pivot의 왼쪽에 있어야하므로 둘의 자리를 바꿉니다.

 

$l$을 6보다 큰 값을 찾을 때 까지 오른쪽으로 움직이다가 8을 찾았습니다.

 

$r$은 6보다 작은 값을 찾을 때 까지 왼쪽으로 움직이다가 3을 찾았습니다.

 

현재 $l$이 가리키고 있는 8는 원래 pivot의 오른쪽에 있어야하고 $r$이 가리키고 있는 3은 pivot의 왼쪽에 있어야하므로 둘의 자리를 바꿉니다.

$l$을 6보다 큰 값을 찾을 때 까지 오른쪽으로 움직이다가 8을 찾았습니다.

 

$r$은 6보다 작은 값을 찾을 때 까지 왼쪽으로 움직이다가 $l$보다 더 왼쪽에 위치하게 되었으므로 더 이상 움직이지 않고 중단합니다.

 

$r$이 가리키는 값은 6 이하임이 보장됩니다. 만약 6보다 컸다면 $l$이 그 곳에 머물러있지, 지나쳐가지 않았을테니까요. 그러므로 $r$이 가리키는 곳과 pivot을 교환하면 pivot을 기준으로 수열을 나누는 과정이 끝납니다.

그 이후엔 Merge Sort와 비슷하게 두 단계로 생각하면 됩니다.

1. 주어진 리스트를 pivot을 기준삼아 2개로 나눈다.
2. 나눈 리스트 2개를 정렬한다.

나눈 리스트 2개를 정렬하는 과정은 마찬가지로 재귀적으로 생각하면 됩니다. 예시 코드를 참고하세요.

 

Quick Sort에서 Pivot을 적절히 잘 선택해 리스트를 적당히 균등하게 잘 나누면 $O(NlgN)$인데 운이 정말 안 좋아 계속 최솟값만을 Pivot으로 잡거나 최댓값만을 Pivot으로 잡아 주어진 리스트를 매우 불균등하게 2개로 나누게 될 경우에는 $O(N^2)$에 동작한다는 매우 중요한 단점이 있습니다.

 

그렇기에 굳이 Quick Sort로 문제를 해결하고 싶다면 제일 앞의 원소만을 Pivot으로 잡으면 절대 안되고 원소 3개를 임의로 골라 중간값을 택한다거나 하는 방식을 사용해야 합니다만 굳이 번거롭게 그러지말고 그냥 Merge Sort를 씁시다.

 

Counting Sort는 앞의 2개 Sort에 비하면 훨씬 쉽습니다. 원소의 종류가 $K$개로 제한되고 그 원소들을 0 ~ $K-1$의 정수에 쉽게 대응할 수 있을 때 정렬을 $O(N+K)$에 수행할 수 있는 정렬법입니다.

 

원소가 1, 2, 3, 4, 5로 한정되어있는 수열을 정렬하기 위해 0x02강에서 다루었던 배열에서의 빈도 조사와 같은 아이디어를 다시 써봅시다. 감이 오시나요?

 

 

 

 

 

 

 

 

 

이렇게 각 원소의 등장 횟수를 셌으면 그냥 각 원소를 등장횟수만큼 적으면 끝입니다.

 

 

 

 

 

 

이 Counting Sort는 특정 범위의 정수를 정렬할 때 유용하게 사용할 수 있습니다. 단 0x01강에서 언급했듯 512MB에 int 변수를 대략 1.2억개 담을 수 있다는 점을 감안하고 메모리 제한을 잘 고려해 Counting Sort를 쓸지 말지 정해야 합니다. 예를 들어 메모리 제한이 128MB인데 수의 범위가 0에서 1억까지라면 Counting Sort를 쓰면 안됩니다. 수가 -1,000,000에서 1,000,000 사이일 때의 예시 코드를 참고하세요.

 

Counting Sort는 구현이 쉽고 수의 범위가 제한적일 때 빠르게 동작하므로 익혀두는 것이 좋습니다.

 

Radix Sort는 자릿수를 이용해 정렬을 수행하는 알고리즘을 Counting Sort를 응용한 버전이라고 생각할 수 있습니다. 그런데 Radix Sort는 구현 과정에서 길이가 정해지지 않은 동적 배열이 필요하고 STL이 없으면 이를 구현하는 것이 다소 껄끄럽습니다.(추후에 그래프를 배울 때 길이가 정해지지 않은 동적 배열을 STL 없이 구현하는 방법에 대해 다루긴 할 것입니다.) 그런데 STL이 있으면 애초에 Radix Sort를 구현할 필요 없이 그냥 STL Sort를 가져다 쓰면 됩니다.

 

그러므로 코딩테스트에서는 Radix Sort 개념을 아예 잊어버리고 있어도 됩니다. 다만 면접이나 손코딩 시험에는 나올수도 있습니다.

 

구체적으로 Radix Sort는 작은 자리 순으로 먼저 정렬을 하고 그 후 상위 자리들을 정렬하는 알고리즘입니다. 10진수를 이용해도 되고 2진수를 이용해도 되고 65536진수를 이용해도 되고 완전 자유인데, 설명의 편의를 위해 10진수를 이용해 정렬을 직접 해보겠습니다.

 

과정을 직접 보면 바로 이해가 갈 것입니다.

 

먼저 1의 자리를 가지고 버킷에 담습니다.

 

 

 

 

 

 

 

 

이제 Counting Sort처럼 각 버킷의 원소를 차례대로 빼서 일의 자리로 정렬한 수열을 만드는데, 버킷 내에 원소가 여러 개일 경우 마치 큐처럼 넣었던 순서대로 나와야합니다. 예를 들어 2번 버킷의 경우 421이 먼저 들어갔으므로 421이 먼저 나오고 이후 21이 나와야 합니다.

 

 

 

 

 

 

 

 

 

 

 

이번에는 10의 자리를 가지고 버킷에 담습니다.

 

 

마찬가지로 순서를 유지하며 10의 자리로 정렬된 수열을 만듭니다.

 

 

마지막으로 100의 자리를 가지고 버킷에 담습니다.

 

순서를 유지하며 100의 자리로 정렬된 수열을 만들면 정렬이 완료됩니다.

 

해당 알고리즘이 왜 올바르게 정렬을 수행하는지 아시겠나요? 잘 이해가 가지 않는다면 수열 내의 두 수 a, b에 대해 a < b일 경우 Radix Sort 과정 중에 언젠가는 a가 b 앞으로 오게 되는 순간이 있다는 점을 생각하면 됩니다.

 

예를 들어 1253와 2512의 경우 100의 자리로 정렬한 이후로 1253이 계속 2512 앞에 있게 되고 65212와 87212의 경우 1000의 자리로 정렬한 이후로 65212가 계속 87212 앞에 있게 됩니다.

 

int 범위일 때 65536(=$2^$)진법으로 처리하면 2번의 자릿수 정렬로 깔끔하게 처리할 수 있습니다. 예시 코드를 참고하세요.

 

Radix Sort를 크기가 적당히 한정된 정수를 정렬할 때에는 유용하게 쓸 수 있지만 실수 혹은 길이가 긴 문자열을 정렬할 때에는 적합하지 않습니다.

 

Radix Sort를 이용해 (x, y, z) 꼴의 좌표를 정렬할 때 유용하게 쓸 수 있습니다. 자연수에서 낮은 자리수부터 정렬한 것 처럼 z, y, x 순으로 정렬을 하면 되기 때문입니다. 

 

그러나 실제 코딩테스트에서는 앞에서 말한 동적 배열의 문제 때문에 Radix Sort를 구현할 일은 없을 것입니다. 개념만 익혀두세요.

 

정렬 알고리즘은 컴퓨터 공학을 전공한 학생이라면 반드시 배우게 되고 또 Merge Sort 정도는 구현할 수 있어야 합니다. 그러나 STL이 허용되는 코딩테스트라면 직접 Sort를 구현할 일은 거의 없습니다. STL의 Sort를 쓰면 되기 때문입니다. 코드를 보시면 알겠지만 딱 한줄로 정렬이 해결되네요.

 

STL의 Sort는 Quick Sort를 기본으로 하되 최악의 경우를 막기 위해 깊이가 어느 정도 이상 깊어지면 Heap Sort를 사용합니다.(Heap Sort는 힙 자료구조를 배운 뒤에 소개해드릴 예정입니다.) 그렇기 때문에 일반적인 Quick Sort와는 다르게 최악의 경우에도 $O(NlgN)$임이 보장되어 마음 편히 사용하면 됩니다. 참고로 이러한 정렬 알고리즘을 Intro Sort라고 부릅니다. 예시 코드를 참고하세요.

 

STL의 Sort에서 필요에 따라 3번째 인자로 내가 지정한 비교 함수를 넘겨줄 수 있습니다. 이 비교 함수는 두개의 인자를 받아 첫 번째 인자가 두 번째 인자보다 앞에 와야 하는 경우 true를 반환해야 합니다.

 

예를 들어 자연수를 5로 나눈 나머지 순으로(5로 나눈 나머지가 같다면 크기 순으로) 정렬하려면 코드와 같이 하면 됩니다. C++11의 람다 함수가 익숙하지 않으면 그냥 외부함수를 이용하면 됩니다.

 

비교 함수는 반드시 아래의 세 조건을 만족해야 합니다.

1. cmp(a, a) = False
2. cmp(a, b) = True이면 cmp(b, a) = False
3. cmp(a, b) = True이고 cmp(b, c) = True이면 cmp(a, c) = True  

이 조건들을 만족하지 않으면 정렬이 이상하게 됩니다. 애초에 2, 3번 조건은 내가 생각한 기준이 저 조건을 만족하지 않으면 그 기준은 정렬을 할 수 없는 기준이니 괜찮은데, 보통 1번 조건을 위배해 cmp(a, a) = True 로 두어서 정렬이 이상하게 수행되어 답이 틀리는 경우가 자주 생기니 실수하지 않도록 주의하세요.

 

2차원 좌표를 x 좌표가 작은 순으로, x좌표가 같다면 y좌표가 작은 순으로 정렬하고 싶으면 직접 클래스를 만들어 비교 함수를 만들어도 됩니다.

 

그러나 굳이 클래스를 만들 필요 없이 STL의 pair를 사용하면 훨씬 간단하게 처리할 수 있습니다. pair간의 대소 비교는 first를 먼저 비교하고 이후 second를 비교하는 방식으로 이미 정의가 되어있기 때문입니다.

 

n차원 좌표를 x, y, z, … 순으로 정렬하고 싶으면 tuple을 사용하면 됩니다. pair와 마찬가지로 미리 대소비교가 정의되어 있습니다. 

 

만약 n=3, 4, 5차원 정도가 아니라 거의 10차원에 육박할 정도로 크다면 대응되는 점을 vector에 넣고 vector를 정렬하면 됩니다. vector끼리도 대소비교가 정의되어 있습니다.

굉장히 긴 강의였네요. 이번 강의를 통해 우선 $O(N^2)$ 에 동작하는 기본적인 정렬 알고리즘인 Bubble Sort을 배웠습니다. 그리고 Bubble Sort보다 더 효율적으로 동작하는 Merge Sort, Quick Sort, Counting Sort, Radix Sort를 배웠습니다. STL Sort의 활용법을 배웠구요.

 

STL이 지원되지 않는 코딩테스트에 응시하게 된다면 Merge Sort, Counting Sort, Bubble Sort를 연습하세요. STL이 지원되는 코딩테스트라면 다른건 다 넘어가고 Counting Sort, STL Sort만 연습하세요. 단 기술면접이나 손코딩 대비를 위해서는 Merge Sort, Quick Sort, Counting Sort, Radix Sort의 특징과 동작 원리를 잘 이해하셔야 합니다.

 

연습 문제를 풀어보면서 이번 시간에 소개한 다양한 정렬법들을 이용해봐도 되고 그냥 STL Sort로 밀어붙여도 상관없습니다.