알고리즘과 자료구조 2강. 줄 세우기와 찾기
100만 명 중에서 한 사람을 찾는 데 스무 번이면 충분합니다. 단, 누군가 미리 줄을 세워 두었을 때만 그렇습니다.
풀고 시작
스무고개가 이기는 이유
1부터 100만 사이의 숫자를 제가 마음에 품었다고 해 봅시다. 하나씩 불러 맞히려 들면 최악의 경우 100만 번을 불러야 합니다. 그런데 "50만보다 큽니까"라고 묻기 시작하면 스무 번 만에 잡아냅니다. 매 질문이 후보를 절반씩 날려 버리기 때문이죠. 이것이 선형 탐색과 이진 탐색(binary search)의 격차입니다. 데이터가 10억 개로 늘어도 이진 탐색은 서른 번이면 끝납니다. 이 마법에는 대가가 있습니다. 반으로 갈랐을 때 "이쪽에는 없다"고 단정하려면 데이터가 미리 정렬되어 있어야 하고, 가운데 원소로 즉시 건너뛸 수 있어야 합니다. 그래서 정렬은 그 자체로 목적이라기보다 이후의 모든 조회를 싸게 만들려고 미리 내는 세금에 가깝습니다. 데이터베이스가 검색 속도를 위해 인덱스를 유지하는 것도, 그 인덱스가 사실상 정렬된 구조인 것도 같은 이유입니다.
손으로 카드를 정리하는 방식
가장 먼저 배우는 정렬은 사람이 실제로 하는 동작을 그대로 옮긴 것들입니다. 버블 정렬은 이웃한 두 장을 비교해 순서가 뒤집혔으면 맞바꾸는 일을 더 이상 바꿀 것이 없을 때까지 반복합니다. 삽입 정렬은 카드 게임에서 손패를 정리하듯 새 카드를 이미 정렬된 왼쪽 부분의 알맞은 자리에 끼워 넣습니다. 둘 다 직관적이고 코드도 짧지만 치명적인 공통점이 있습니다. 원소 하나를 제자리에 놓기 위해 남은 원소들을 훑기 때문에, 전체 비교 횟수가 데이터 개수의 제곱에 비례합니다. 1000개면 100만 번, 100만 개면 1조 번입니다. 데이터가 열 배 늘면 시간은 백 배 늘죠. 다만 삽입 정렬은 이미 거의 정렬된 데이터에서는 놀랄 만큼 빨라서, 오늘날의 표준 라이브러리도 작은 조각을 마무리할 때는 여전히 삽입 정렬을 씁니다.
반으로 쪼개는 발상
돌파구는 문제를 잘게 나누는 데서 나왔습니다. 병합 정렬(merge sort)은 배열을 절반으로 자르고, 각 절반을 같은 방식으로 정렬한 다음, 정렬된 두 줄을 앞에서부터 하나씩 비교해 합칩니다. 폰 노이만이 1945년에 기술한 것으로 알려진 이 방법의 비용을 따져 보죠. 합치는 작업은 전체 원소를 한 번씩 훑으니 n번이고, 절반으로 자르는 일은 log n번이면 바닥에 닿습니다. 그래서 총비용이 n log n입니다. 100만 개라면 1조 번이 2000만 번으로 줄어듭니다. 퀵 정렬은 토니 호어가 1959년 러시아어 문장을 다루던 중 단어를 정렬할 일이 생겨 고안한 방법으로, 기준값(피벗)을 하나 정해 그보다 작은 것과 큰 것으로 갈라놓은 뒤 양쪽을 각각 같은 방식으로 처리합니다. 평균은 n log n이지만 피벗을 계속 잘못 고르면 최악에는 제곱으로 되돌아갑니다. 그럼에도 실전에서 널리 쓰이는 이유는 추가 메모리를 거의 쓰지 않고 메모리 접근이 연속적이어서 실제 상수가 작기 때문입니다. 나누고 각각 풀어 합치는 이 분할 정복(divide and conquer) 전략은 이후 수많은 알고리즘의 기본 골격이 됩니다.
더 빨라질 수는 없을까
여기서 놀라운 질문이 나옵니다. 언젠가 천재가 나타나 n log n보다 빠른 정렬을 발명할 수 있을까요. 비교만으로 정렬하는 한 답은 "없다"이고, 그것은 추측이 아니라 증명된 사실입니다. 논증은 이렇습니다. n개 원소가 놓일 수 있는 순서는 n!가지이고, 알고리즘은 그중 정답 하나를 지목해야 합니다. 비교 한 번이 주는 정보는 "예" 아니면 "아니오", 즉 갈래 두 개뿐이므로 k번 비교로 구별할 수 있는 경우의 수는 최대 2의 k제곱입니다. 따라서 2의 k제곱이 n! 이상이어야 하고, 정리하면 k는 최소한 n log n 규모가 됩니다. 이것이 비교 기반 정렬의 하한입니다. 흥미롭게도 이 벽은 전제를 바꾸면 우회됩니다. 값이 0에서 100 사이의 정수라는 사실을 알고 있다면, 비교하지 않고 각 값이 몇 개인지 세기만 해도 정렬이 끝나죠(계수 정렬). 하한을 깬 것이 아니라 비교라는 링 밖으로 나간 것입니다.
같은 점수인데 순서가 바뀌면
마지막으로 실무에서 자주 사고를 내는 개념 하나를 짚겠습니다. 성적표를 이름순으로 정렬해 둔 다음 점수순으로 다시 정렬했더니, 같은 점수를 받은 학생들의 이름 순서가 뒤죽박죽이 됐다고 해 봅시다. 이런 일이 벌어지지 않는 정렬을 안정 정렬(stable sort)이라고 합니다. 값이 같은 원소들의 원래 상대 순서를 그대로 보존한다는 뜻이죠. 병합 정렬은 합칠 때 같은 값이면 앞쪽 줄의 원소를 먼저 집도록 만들 수 있어 안정적이고, 퀵 정렬은 멀리 떨어진 원소끼리 자리를 맞바꾸므로 일반적인 구현에서는 불안정합니다. 정렬을 여러 번 겹쳐 적용해 다중 기준을 만드는 흔한 기법은 안정성 위에서만 성립합니다. 그리고 이 모든 이야기는 데이터를 어떤 그릇에 담았느냐에 다시 좌우됩니다. 다음 강의 주제입니다.
인출 문제
이전: 알고리즘과 자료구조 1강 · 다음: 알고리즘과 자료구조 3강