수열에서 중간값 찾기 문제와 분할/정복 알고리즘의 정수

1. 중간값 찾기 문제

 

임의의 N개의 원소를 가진 수열이 주어졌을 때, 그 중간값을 찾는 문제다. 여기서 중간값이란 그 값을 기준으로 작은 모든 원소들과 그 값보다 큰 모든 원소들을 이등분하는 값을 말한다.

 

간단하게 생각하면 정말 정의 그대로, 그냥 주어진 배열을 정렬하고 중간에 있는 값을 선택하면 될 것 같다. 물론 그렇게 해도 풀리며, O(N logN) 정렬 알고리즘을 선택해 사용하면 될 것이다.

 

그러나 이렇게 푸는 것은 매우 아쉽다. 컴퓨팅 사고력에서 중요한 능력 중 하나는 쓸데없는 계산을 줄이는 것이라고 배웠다. 지금 문제는 중간값을 찾으면 되지, 굳이 정렬까지 할 필요는 없다. 위치만 알면 되기 때문이다.

 

나는 이 문제를 N/2 크기의 힙(Heap) 자료구조를 이용하는 식으로 생각했다. Min Heap이다. 수열 전체를 쭈욱 스캔하면서 하나씩 힙에 넣고, 그 결과로 나온 최솟값을 하나씩 빼서 다른 수열에 넣는다. 이 과정을 반복하면 수열에는 작은 값들이 나열되어 있게 된다. 여기서 최댓값을 찾으면 그것이 중간값이다.

 

나는 처음 이 문제를 이렇게 풀면서 속으로, "Heap에 넣는 식이니까 굳이 정렬을 하지는 않지. 따라서 정렬이라는 쓸데없는 계산을 피한거야." 라고 생각했다. 하지만 안타깝게도 아니었다... 특별히 퍼포먼스가 개선되는 것도 아니다.

 

 

2. 힙 사용 방식에서 더 개선하기. (feat. 퀵 정렬)

이 방식에는 문제가 있었다. 알고보니 쓸데없는 계산이 또 있었던 것이다. 힙 내부에서 삽입된 데이터를 배치할 때 내부적으로 트리에서 비교 연산들이 수행되고 있었던 것이다. 물론 최솟값을 찾기 위해서는 그런 연산이 수행되어야 한다. 하지만 아쉬운 방식이다.

 

여기서 좋은 풀이는 분할 정복 프로그래밍을 사용하는 것이다. 분할 정복이란, 문제들을 하위 문제들로 나누어서 하위 문제가 구축한 정보를 바탕으로 정복하자는 개념이다. 분할 정복에도 종류가 여러 가지가 있지만, 본질은 정보를 구축하는 것이다. 그렇게 쓸데없는 중복된 계산을 피한다.

 

여담이지만, 퀵 정렬은 이 정보를 구축하는 방식이 약간 다르다. 병합 정렬이 일단 데이터를 나누고 정렬한 뒤, 그 정렬된 정보를 바탕으로 merge 하는 개념이라면, 퀵 정렬은 데이터를 나누는 시점에서 정보를 구축한다. 즉, 분할/정복은 분할 알고리즘과 정복 알고리즘으로 나뉘는데, 정복 알고리즘이 데이터를 분할하는 과정에서 조금 더 힘을 들일 수도 있고(퀵 정렬), 혹은 데이터를 단순 등분한 뒤 하위 문제들이 조금 더 힘을 들여서 정보를 구축할 수도 있는 것이다.(합병 정렬) 물론 어떤 방식이든 하위 문제들의 정보를 바탕으로 정복 알고리즘이 힘 쓴다는 사실은 변함이 없다.

 

 

중간값 찾기 문제의 좋은 풀이법이 이러한 퀵정렬의 분할/정복 방식을 따르기 때문에 소개해봤다. 그럼 퀵 정렬의 분할/정복 프로그래밍의 아이디어를 이용해 중간값을 찾으려면 어떻게 해야 할까? 쓸데없는 계산을 피하면 된다. 굳이 모든 원소를 퀵하게 정렬할 필요는 없다는 것이다.

 

일단 pivot값을 토대로 좌우를 나누었으면, 양 수열의 길이 정보를 이용한다. 그 비율이 50:50이라면 축하하자! 한 번에 찾았다. 물론 이런 운이 언제나 따르지 않는다. 예를 들어, pivot이 40:60으로 나뉜다면 적어도 중간값은 50보다 큰 60 쪽에 있을 것이다. 따라서 왼쪽 수열을 쳐낸다. 바로 이 부분에서 쓸데없는 계산을 없앤다.

 

다음에는 같은 논리를 그대로 이용한다. 오른쪽 수열을 대상으로 한다. pivot을 선택해 작은 값과 큰 값을 나눈다. 그러면 그 pivot의 원래 배열의 크기에 대한 위치를 알 수 있다. 그 위치가 50이면 축하! 그러나 만약 45라면? 이번에도 오른쪽 수열에 있다.... 이런 식이다.

 

이 알고리즘은 분할 시점에서 이미 정보를 구축한다. 정복 단계에서 힘 깨나 쓰는 방식이다. pivot을 토대로 왼쪽 수열이 pivot 보다 작고, 오른쪽 수열이 pivot 보다 크다는 정보를 발생시키는 구조다. 이때 하위 모듈은 pivot 좌우의 길이 정보를 밝혀내 정복 단계의 알고리즘에게 전달한다. 정복 알고리즘이 이를 이용하면 효율적으로 쓸데없는 데이터를 판단하고 쳐내는 것이다.

 

 

3. 수열이 여러 서버에 분산되어 있을 때는?

그러나 나는 퀵 정렬에 숨은 분할/정복 프로그래밍의 본질을 제대로 이해하지 못했던 것 같다. 그래서 다음 문제를 풀 수가 없었다. 

 

임의의 거대한 수열이 N개의 서버에 분산되어 저장되어 있다. 여기서 전체 수열에 대한 중간값을 찾으려면?

 

분산이라는 말에 혹해버렸다. 하하.. 속았다. 분산되어 있기 때문에 나도 모르게 이 문제의 풀이 구조가 분할/정복 알고리즘이라고 생각했다. 틀린 판단은 아니었다. 하지만 이미 분할되어 있으니까 각 수열에 대해 각 서버들이 중간값을 찾으려고 시도하면 되지 않을까...? 라고 무의식적으로 생각해버렸다. 물론 이 방식은 당연히 틀렸다.

 

일단 이 문제 또한 당연히 분할/정복 프로그래밍에 속한다. 그러나 단순히 분할 정복을 수열을 나눠서 개별적인 알고리즘을 수행하는 프로그래밍이라고 자꾸 착각을 해버리니까 실수를 하는 것이다. 다시 말하지만 분할/정복은 정복 단계에서, 분할된 각 하위 문제들이 밝혀낸 정보를 이용하는 것이다.

 

각 서버가 자신들의 수열에서 중간값을 찾는다고 해보자. 그런데 이 정보가 전체 수열에서 중간값을 찾는 단계, 즉 정복 단계에서 유용하게 사용이 되나? 나는 바로 이걸 물었어야 했다... 이걸 하지 않은게 내 패인이었다...

 

(난 아직도 분할/정복 프로그래밍의 진수를 내 몸에 새기질 못한 것 같다.. 열심히 하자...)

 

 

여하튼! 질문에 답하자면 당연히 전혀 쓸데 없는 정보다. 각 수열의 중간값 m1, m2, m3, ... 들이 도대체 무슨 소용인가? 아무런 쓸모도 없다!! 각 서버에 분산된 수열들이 원래 수열 전체에서 어떤 위치에 배치될지 상상해보자. 각 수열의 원소들은 원래 전체 수열의 이곳 저곳 산발되어 있을 것이다. 따라서 각 수열의 중간값들은 원래 중간값과 아무런 관계가 없다.

 

이것은 분할/정복 알고리즘에서 정복 단계가 핵심이라는 사실을 놓쳐서 실수하는 것이다. 정복자 (즉, 이 경우에는 중앙 컴퓨터가 되겠는데), 중앙 컴퓨터가 정복 알고리즘을 어떻게 설계해야 할까? 정복 단계에서 알고 싶은 것은 어떤 원소가 50% 위치에 속한 값인지 알고 싶은 것이다. 만약 원래 수열 전체가 주어졌다면 퀵 정렬을 응용해 위에서 설명한 대로 풀면 된다. 그러나 그 수열의 원소들이 서버 컴퓨터 이곳저곳 산발되어 있어서 그렇게 풀 수 없다.

 

좋은 알고리즘이라면 정복 단계에서, 각 서버가 풀어준 정보를 바탕으로 결과를 쉽게 판단할 수 있어야 할 것이다. 따라서 핵심은 어떤 정보를 받아야 할지다. 이것은 정복 알고리즘이 결정해야 할 문제다.

 

해답은 이렇다. 정복자 중앙 컴퓨터는 임의의 pivot을 선택해 각 서버 컴퓨터에 뿌린다. 그리고 각 서버는 해당 pivot에 대해 작은 값과 큰 값의 길이 정보 (min, max)를 구축할 수 있다. 이 정보를 중앙에 전달하자. 그러면 정복자는 하위 문제들이 전달한 min, max의 sum을 구할 수 있다. 즉, pivot의 전체 수열에서 차지하는 위치를 알 수 있는 것이다. 만약 min = max라면 축하! 문제를 풀었다. 만약 min < max 라면? pivot이 왼쪽으로 치우쳐진 상태다. 그러면 pivot을 오른쪽으로 조정할 수 있다. 그리고 다시 똑같은 논리를 수행하면 된다. 반복하면 결국 중간값을 찾아내는 것이다.