분할 정복의 진정한 핵심은 정보 구축하기! (feat. 합병 정렬)

1. 합병 정렬(Merge Sort)이란?

정렬이란 임의의 데이터 배열을 일정한 규칙에 따라 배열하는 알고리즘을 말하며, 그 종류는 여러 가지가 있다. 기초 알고리즘 수업 시간에 다루는 정렬 알고리즘에는 "버블 정렬", "선택 정렬", "삽입 정렬", "합병 정렬", "퀵 정렬", ... 등이 있다. 이 중에서 버블과 선택, 그리고 삽입 정렬은 인간의 직관적인 정렬 방식을 그대로 프로그래밍 언어로 풀이한 것으로서, 사실상 컴퓨터 과학에서 다룰 가치가 전혀 없다. 데이터 개수(N)가 증가할수록 N의 제곱으로 처리량이 증가하기 때문이다.

(여담이지만 직관적인 방식으로 알고리즘을 풀면 보통 쓸만한 알고리즘이 나오지 않는 것 같다.)

 

그러나 합병 정렬부터는 실질적으로 사용할 수 있다. 시간복잡도가 O(N logN)이기 때문이다. 그런데 어째서 똑같은 배열인데도 불구하고 합병 정렬은 시간복잡도가 개선되는 것일까? 대학에서 교양으로 배운 자료구조 수업 시간에 처음 합병 정렬을 풀었을 때, 나는 아무리 생각해도 어떤 원리로 시간 복잡도가 개선되는 것인지 그 원리를 포착할 수 없었다. 오히려, '문제를 나눠서 문제가 기하급수적으로 늘어난 거 아닌가? 그런데 왜 좋아진거지???' 하는 의문도 있었다.

 

이후 알고리즘을 풀어보며 실력을 키우는 과정에서 뒤늦게나마 어째서 합병 정렬, 더 나아가 "분할 정복" 프로그래밍이 우수한 것인지 깨닫게 되었다.

 

 

2. 분할 정복은 단순히 문제를 나누라는 뜻이 아니다.

프로그래밍을 배울 때 지겹도록 듣는 단어인 "분할 정복, Divide and Qonquer"을 처음 들었을 때, 나는 그 단어의 의미를 직관적으로만 생각했던 것 같다. 프로그래밍에 익숙하지 않았던 비전공자인 나는 분할 정복의 진정한 의미를 이해하지 못하고, 그저 알고리즘 문제를 차근차근 단계적으로 풀라는 말이구나... 하는 식으로만 받아들였던 것이다.. (그렇다.. 난 프로그래밍 재능이 없었던 것이다... 그래서 지금 이렇게 노력한다...)

 

그러나 분할 정복은 단순히 문제를 알아서 나누라는 것 이상의 의미를 갖추고 있다. 실제로 분할 정복 프로그래밍의 대표적 예시인 합병 정렬은 시간 복잡도가 개선된다!! 즉, 분할 정복은 실제로 퍼포먼스를 개선하는 검증된 방식이다. 읽기 쉽도록 문제를 나눠 가독성을 높이거나, 풀이 단계를 차근차근 생각해보라는 단순한 의미가 아닌 것이다!! 분명히 분할 정복의 배후에는 수학적 원리가 숨어 있다. 이것의 정체를 밝혀내야 비로소 분할 정복을 정복할 자격이 있다고 말할 수 있을 것이다.

 

내가 온갖 책들을 읽어가며 이해한, 분할 정복의 진정한 의미를 직관적으로 표현하면 다음과 같다.

 

큰 문제를 작은 문제들로 분해하라. 그리고 그 문제를 해결하라. 
이때, 작은 문제를 해결하는 과정에서 정보가 구축된다. (핵심이다!)
큰 문제는 작은 문제들이 구축한 정보를 바탕으로 효율적으로 결과를 병합할 수 있다.

 

 

3. 시간 복잡도가 개선되는 이유는 쓸데없는 계산을 제거하기 때문.

"분할 정복"에서 진짜 중요한 단어를 꼽자면, 나는 분할이 아니라 정복이라고 생각한다.

 

정복은 그저 하위 문제들이 해결한 결과를 합하는 과정이라고 여기기 쉽다. 그러나 중요한 것은 왜 하위 문제를 다 풀고 난 다음, 결과들을 합하는 것이 쉬워졌는지 의문을 가져보는 것이다.

 

잠깐 반대로 생각해보자. 왜 랜덤한 수열을 오름차순(혹은 내림차순)으로 배열하는 것이 그토록 어려운 것일까? 일단 임의의 어떤 수열이 주어지면 그 순서를 정하기 위해 모든 원소들을 차례대로 방문해야 할 것이다. 보통 이렇게 생각하기 쉽고, 틀린 생각도 아니다. 아무리 알고리즘이 개선되어도 시간복잡도는 O(N)일 것 같다.

 

그러나 만약 그 수열이 완전한 랜덤이 아니라면 어떻게 될까? 정보이론 식으로 표현하자면 정보량이 적은 수열이라면? 예를 들어, 수열을 이등분했을 때 이미 앞 부분은 독립적으로 오름차순 정렬되어 있고, 뒷 부분 또한 독립적으로 오름차순 정렬되어 있다는 사실을 알게 되었다고 해보자. 배치 규칙이 있기 때문에 아마 수열을 반으로 쪼개서 수열의 앞 부분의 원소들과, 뒷 부분의 원소들을 하나씩 비교하며 새로운 수열에 담으면 된다.

 

수학적으로 상상해보자. A > B > C > ... 순서로 정렬된 수열이 있을 때, 어떤 임의의 수 X가 A보다 크다면, X > B, X > C, .. 인 것은 자명하다. 따라서 X는 A 앞에 배치하면 된다. 계산 끝이다. 구태여 B, C, D, E, ... 와 X를 비교할 필요가 없다. 전부 쓸데없는 계산이다.

 

버블 정렬이나 삽입 정렬의 문제는 바로 이것이다. 이 녀석들은 쓸데없는 계산을 해버린다. 처음부터 주어진 배열을 통째로 풀어버리려고 시도하니, 어쩔 수 없이 모든 원소 사이의 비교 계산을 해야 한다. 그러나 생각해보면, 두 원소 간 우선순위를 비교했다면 그 정보는 소중하지 않은가? 하지만 버블이나 삽입 정렬 등은 그러한 정보를 이용하질 않는다. 그러니 자꾸 쓸데없는 계산, 한 번 들쑤어 본 원소를 또 보고 또 보는 것이다..

 

합병 정렬의 핵심은 큰 문제를 작은 하위 문제로 쪼개어 각 문제들을 풀었을 때, 바로 그 결과들에 정보가 구축되었다는 점을 활용한 것이다. (참고로 말하지만, 합병 정렬은 재귀가 중심이 아니다!!) 이렇게 쓸데 없는 계산을 피한다. 어떤 식으로 수열이 배열되었는지 그 규칙을 알 수 있으므로 병합이 너무나 쉬워진 것이다. 하위 문제들이 풀어준 수열 두 개를 한 번만 주~욱 훑어보면 끝이다! ( BigO = O(N) )

 

 

4. 분할 정복은 정복 과정이 핵심!

분할 정복 프로그래밍에서 핵심이 merge 파트라는 것을 나는 너무 늦게 깨달은 것 같다. 함수를 만들고, 클래스를 만드는 과정에서 모두 "분할"을 강조하다보니, 나는 그것이 분할정복 프로그래밍에서 말하는 분할과 같다고 착각했다.

 

그러나 합병 과정이 핵심이었다. 합병 과정에서 과연 이전의 하위 문제들이 풀어준 결과에서 구축된 정보를 바탕으로 쓸데 없는 계산을 피할 수 있는가가 본질이었다.

 

극단적인 예시를 들어 보겠다. 예를 들어, 1등 정하기 문제를 생각해보자. 100명의 사람들이 경쟁을 한다. 이 중에서 1등을 뽑고 싶다. A가 B를 이기고, B가 C를 이기면 자동으로 A는 C보다 강하다고 가정하자. 과연 이 사람들을 대상으로 정말로 EPL 프리미어리그 마냥 한 번씩 서로 경쟁을 해서 결과를 내야 할까?? A가 B를 이기고, B가 C를 이기면 구태여 A와 C가 싸워야 할까? 이전의 정보를 이용한다는 말은 이것이다.

 

#. 결론

분해를 할 수 있다. 그러나 분해를 해서 얻은 결론을 바탕으로 더 간단하게 합병할 수 있어야 한다. 만약 분해를 했음에도 이전과 비교해 복잡도가 전혀 개선된 것이 없다면, 합병(정복) 과정에서 하위 문제들이 구축한 정보를 전혀 이용하질 않거나 일부 누락했다는 것이다. 또는 어쩌면 그건 분할 정복에서 말하는 분할이 아니라, 분산 컴퓨팅이 필요한 상황일지도 모른다.