여러 가지 알고리즘

친구가 1부터 1000 사이의 수 하나를 마음속에 정했다. 내가 수를 말하면 친구는 "더 커", "더 작아", "맞아" 가운데 하나로 답한다. 1부터 차례로 물으면 최악의 경우 1000번이 걸리지만, 매번 남은 범위의 한가운데를 물으면 10번 안에 반드시 맞힐 수 있다고 한다. 또 반 학생 100명의 시험 점수를 차례로 정렬할 때, 이웃한 두 점수를 비교해 바꾸는 방법은 4950번 비교하지만 다른 방법은 600번 남짓이면 된다. 같은 일을 하는 알고리즘인데 왜 이렇게 차이가 날까?

2.5.1절반씩 버리는 탐색

정렬된 범위에서 수를 찾을 때 한가운데를 물으면, 답이 무엇이든 남은 범위가 절반으로 준다. 1000개의 후보가 500개, 250개, 125개로 줄어들어 10번이면 1개가 남는다. \(2^{10} = 1024\)이 1000보다 크기 때문이다. 이것이 이진 탐색이다. 후보가 백만 개로 늘어도 20번, 10억 개여도 30번이면 된다. 반면 하나씩 묻는 순차 탐색은 후보 수만큼 물어야 하므로, 후보가 많을수록 두 방법의 차이는 엄청나게 벌어진다. 다만 이진 탐색은 자료가 크기 순으로 정렬되어 있어야 쓸 수 있다.

거품 정렬은 이웃한 두 수를 비교해 큰 수를 뒤로 보내는 일을 되풀이해, 한 바퀴 돌 때마다 가장 큰 수가 맨 뒤로 간다. 모든 쌍을 비교하는 셈이어서 비교 횟수가 \(n^2\)에 비례한다. 병합 정렬은 자료를 절반으로 나누어 각각 재귀적으로 정렬한 뒤, 정렬된 두 묶음을 앞에서부터 비교하며 합친다. 나누는 단계가 \(\log_2 n\)번이고 각 단계에서 합치는 비교가 \(n\)번 정도이므로 \(n\log_2 n\)에 비례한다. 그래서 자료가 많을수록 절반씩 나누는 방법이 크게 유리하다.¹

2.5.2자료가 커지면 차이도 커진다

알고리즘의 효율은 자료의 크기 \(n\)이 커질 때 계산량이 어떻게 늘어나는지로 비교한다. 자료가 100개일 때 거품 정렬과 병합 정렬의 비교 횟수는 8배쯤 차이 나지만, 100만 개이면 \(n^2/2 \approx 5\times10^{11}\)과 \(n\log_2 n \approx 2\times10^7\)으로 2만 배 넘게 차이 난다. 1초에 비교를 10억 번 하는 컴퓨터로도 거품 정렬은 8분 넘게, 병합 정렬은 0.02초쯤 걸린다. 그래서 큰 자료를 다루는 프로그램에서는 알고리즘의 선택이 컴퓨터의 속도보다 훨씬 중요하다.

2.5.3예제 풀이

범위 1~1000에서 500을 물으면 "더 커"이므로 501~1000이 남는다. 750을 물으면 "더 작아"로 501~749, 625를 물으면 "더 커"로 626~749, 687을 물으면 "더 커"로 688~749, 718을 물으면 "더 작아"로 688~717, 702를 물으면 "더 작아"로 688~701, 694를 물으면 "더 커"로 695~701, 698을 물으면 "더 커"로 699~701이 남고, 700을 물어 "맞아"이다. 모두 9번이다.

한 번 물을 때마다 남은 후보가 절반 이하로 줄어, \(k\)번 물은 뒤 남은 후보는 \(1000/2^k\) 이하이다. \(2^{10} = 1024 > 1000\)이므로 10번이면 후보가 한 개 이하가 되어 반드시 맞힌다. 반대로 9번으로는 \(2^9 = 512\)가지밖에 구별할 수 없어 어떤 수는 맞히지 못한다. 즉 같은 일을 하는 알고리즘도 문제를 어떻게 줄여 가느냐에 따라 효율이 크게 다르며, 이진 탐색과 병합 정렬처럼 절반씩 나누는 방법은 자료가 커질수록 하나씩 처리하는 방법보다 훨씬 빠르다.

아래 탐구 카드에서 여러 정렬 방법의 비교 횟수를 직접 세어 경주시켜 보고, 1부터 1000까지의 수를 몇 번 만에 맞히는지 확인해 보자.

1. 비교만으로 정렬하는 어떤 알고리즘도 최악의 경우 \(\log_2(n!)\)번보다 적게 비교할 수 없다는 것이 증명되어 있다. \(n!\)가지 배열을 구별하려면 예, 아니오로 답하는 질문이 그만큼 필요하기 때문이며, 이 값이 대략 \(n\log_2 n\)이어서 병합 정렬은 거의 가장 빠른 방법이다.