컴퓨터는 「어디 있나」를 한눈에 알지 못한다
한 칸씩 「여기인가?」를 물어 가며 찾습니다.
책상 위에 흩어진 열쇠 뭉치에서 내 사물함 열쇠를 고르는 일, 연락처에서 친구 이름을 찾는 일, 사전에서 모르는 단어를 찾는 일. 모두 여럿 가운데 원하는 하나를 골라내는 일입니다.
탐색(search)
여러 데이터 가운데 내가 찾는 것 하나를 집어내는 일입니다. 출발점에서 목표에 이르는 경로를 찾는 일도 탐색이라고 부르지만, 여기서 찾는 것은 경로가 아니라 값 하나입니다.
우리가 책장을 볼 때는 눈이 여러 권을 동시에 살피기 때문에 「저기쯤 있겠다」는 짐작이 먼저 섭니다. 컴퓨터에게는 그런 짐작이 없습니다. 여기서 볼 두 방법에서 컴퓨터가 하는 일은 어느 한 칸을 콕 집어 「여기 있는 것이 찾는 값인가?」라고 묻는 것입니다.
그래서 탐색 알고리즘은 「묻는 차례」를 정하는 일입니다
한 번 물어서 알 수 있는 것은 「맞다」 또는 「아니다」, 그리고 순서대로 놓여 있을 때는 「찾는 값이 이보다 큰가 작은가」 정도입니다. 그렇다면 어느 칸을 먼저 물을 것인가가 전부입니다. 잘 고르면 몇 번 만에 끝나고, 잘못 고르면 끝까지 물어야 합니다. 순차 탐색과 이진 탐색은 이 「묻는 차례」가 다를 뿐입니다.
오늘 찾을 책장
책 열다섯 권이 번호가 작은 것부터 꽂혀 있습니다. 칸의 위치는 인덱스(index)로 말하겠습니다. 인덱스는 맨 앞 칸에서 몇 칸 떨어져 있는지를 나타내는 번호라서, 맨 앞 칸이 인덱스 0이고 그다음이 인덱스 1입니다. 파이썬 같은 프로그래밍 언어도 이렇게 셉니다. 이 책장에서 번호 73인 책을 찾는 것이 오늘의 문제입니다.
위 줄의 회색 숫자는 인덱스, 아래 칸의 검은 숫자는 그 칸에 꽂힌 책의 번호입니다. 둘을 헷갈리지 않도록 조심하세요.
오늘 하루 동안 무언가를 찾은 일을 두 가지 떠올려 보세요. 그중 하나는 순서대로 정리되어 있는 곳에서 찾았고, 다른 하나는 그렇지 않았을 것입니다. 어느 쪽이 더 빨랐나요?
순차 탐색 — 맨 앞부터 하나씩 물어본다
가장 단순하고, 어떤 책장에서도 통합니다.
가장 먼저 떠오르는 방법은 맨 앞 칸부터 차례로 물어보는 것입니다. 「인덱스 0이 73인가? 아니네. 인덱스 1은? 아니네…」 이렇게 앞에서부터 하나씩 확인해 나가는 방법을 순차 탐색(sequential search)이라고 합니다.
순차 탐색의 규칙
- 인덱스 0부터 시작한다.
- 그 칸의 값이 찾는 값과 같으면 멈춘다. 찾은 것이다.
- 다르면 한 칸 오른쪽으로 옮겨 2를 반복한다.
- 마지막 칸까지 갔는데도 없으면 「없다」로 끝낸다.
73을 찾아보면
분홍색이 지금 물어보고 있는 칸, 회색이 이미 물어본 칸입니다.
1번째 확인 — 인덱스 0은 4. 73이 아니다
2번째 확인 — 인덱스 1은 9. 역시 아니다
이렇게 한 칸씩 오른쪽으로 옮겨 가며 열두 번째 확인까지 묻습니다.
13번째 확인 — 인덱스 12가 73. 찾았다
73은 인덱스 12, 곧 앞에서 열세 번째 칸에 있었으므로 값을 열세 번 확인하고 나서야 찾았습니다.
순차 탐색은 운에 크게 좌우됩니다. 찾는 값이 맨 앞 칸에 있으면 한 번이면 끝나지만, 마지막 칸에 있거나 아예 없으면 열다섯 번을 모두 물어야 합니다. 「없다」는 답을 내려면 빠짐없이 다 봐야 하기 때문입니다.
좋은 점
- 순서가 뒤섞여 있어도 됩니다. 뒤죽박죽인 책장에서도 그대로 통합니다.
- 규칙이 단순해 실수할 여지가 적습니다.
걸리는 점
- 데이터가 많아지면 확인할 칸도 그만큼 많아집니다.
- 한 번 물어 알아낸 것이 다음 물음을 좁혀 주지 못합니다.
이 책장에서 순차 탐색으로 번호 90을 찾을 때와 책장에 없는 번호 50을 찾을 때, 확인 횟수는 둘 다 열다섯 번입니다. 횟수가 같은데도 두 경우가 다른 점은 무엇일까요?
이진 탐색 — 한 번 물을 때마다 절반을 버린다
사전을 찾을 때 우리가 이미 쓰고 있는 방법입니다.
사전에서 「소나기」라는 단어를 찾는다고 해 봅시다. 1쪽부터 넘기는 사람은 없습니다. 가운데쯤을 열어 보고, 거기가 「ㅈ」이면 「소나기」는 앞쪽이니 뒤쪽 절반은 통째로 버립니다. 그리고 남은 앞쪽 절반에서 다시 가운데를 엽니다.
이렇게 가운데 값과 비교해 범위를 절반씩 줄여 가며 찾는 방법을 이진 탐색(binary search)이라고 합니다. 「이진」은 둘로 나눈다는 뜻입니다.
이진 탐색은 정렬되어 있어야 합니다
사전이 가나다순이 아니라면 가운데를 열어 봐야 아무것도 알 수 없습니다. 「여기가 ㅈ이니 앞쪽에 있겠다」는 판단은 순서대로 놓여 있다는 것을 알기 때문에 할 수 있는 것입니다. 이진 탐색은 순서가 뒤섞인 데이터에는 아예 쓸 수 없습니다.
이진 탐색의 규칙
- 찾을 범위를 책장 전체로 잡는다.
- 범위의 가운데 칸을 정해 그 값을 확인한다.
- 찾는 값과 같으면 멈춘다. 찾은 것이다.
- 찾는 값이 더 작으면 가운데의 왼쪽만, 더 크면 오른쪽만 남기고 2로 돌아간다.
- 남은 범위가 없어지면 「없다」로 끝낸다.
가운데 칸은 이렇게 정합니다
(앞쪽 끝 인덱스 + 뒤쪽 끝 인덱스) ÷ 2, 나누어떨어지지 않으면 소수점 아래를 버립니다. 예를 들어 범위가 인덱스 8부터 14까지라면 (8 + 14) ÷ 2 = 11이므로 인덱스 11이 가운데입니다. 범위가 인덱스 12부터 14까지라면 (12 + 14) ÷ 2 = 13이므로 인덱스 13입니다.
같은 73을 이진 탐색으로
노란색이 가운데 칸, 흐린 칸이 범위에서 빠진 칸입니다.
인덱스 0~14 — 가운데는 인덱스 7의 42. 42 < 73 이므로 오른쪽만 남긴다
인덱스 8~14 — 가운데는 인덱스 11의 68. 68 < 73 이므로 오른쪽만 남긴다
인덱스 12~14 — 가운데는 인덱스 13의 81. 81 > 73 이므로 왼쪽만 남긴다
인덱스 12~12 — 가운데는 인덱스 12의 73. 찾았다
값을 네 번 확인하고 찾았습니다. 순차 탐색으로는 열세 번이 걸리던 값입니다.
왜 이렇게 줄어들까요? 한 번 물을 때마다 남은 범위가 절반이 되기 때문입니다. 실제로 범위가 15칸 → 7칸 → 3칸 → 1칸으로 줄었습니다. 순차 탐색이 한 번에 한 칸씩 지워 나가는 것과 대조됩니다.
좋은 점
- 데이터가 많아져도 확인 횟수가 천천히 늘어납니다.
- 찾는 값이 없을 때도 빨리 끝납니다. 범위가 금방 사라지기 때문입니다.
걸리는 점
- 정렬되어 있어야만 쓸 수 있습니다.
- 중간에 책을 끼워 넣거나 빼면 다시 순서를 맞춰 두어야 합니다.
이 책장에서 이진 탐색으로 번호 42를 찾으면 몇 번 확인할까요? 답이 왜 그렇게 작은지, 가운데 칸을 계산해 확인해 보세요.
그래서 늘 이진 탐색을 쓰면 될까
숫자를 몇 개 더 세어 보면 답이 그렇게 간단하지 않습니다.
73을 찾을 때는 열세 번과 네 번, 차이가 컸습니다. 그런데 찾는 값을 바꾸어 보면 이야기가 달라집니다. 같은 책장에서 세 가지 값을 찾아 확인한 횟수를 세어 보았습니다.
| 찾는 값 | 순차 탐색 | 이진 탐색 | 어떻게 된 것인가 |
|---|---|---|---|
| 73 (인덱스 12) | 13번 | 4번 | 뒤쪽에 있을수록 순차 탐색이 불리합니다. |
| 4 (인덱스 0) | 1번 | 4번 | 맨 앞에 있으면 순차 탐색이 한 번에 끝납니다. 이쪽은 순차 탐색이 빠릅니다. |
| 50 (책장에 없음) | 15번 | 4번 | 없다는 답을 내려면 순차 탐색은 전부 봐야 합니다. |
「이진 탐색이 더 빠르다」고 잘라 말할 수 없습니다
번호 4를 찾을 때는 순차 탐색이 한 번, 이진 탐색이 네 번이었습니다. 이진 탐색은 언제나 가운데부터 묻기 때문에, 찾는 값이 맨 앞에 있어도 가운데를 먼저 거쳐야 합니다. 이진 탐색이 힘을 내는 것은 데이터가 많고, 찾는 값이 어디 있을지 모를 때입니다.
정렬은 공짜가 아니다
더 중요한 것이 있습니다. 이진 탐색을 쓰려면 먼저 책을 번호순으로 꽂아 두어야 합니다. 그 정리하는 일에도 시간과 노력이 듭니다. 그래서 「어느 탐색이 빠른가」만 비교해서는 답이 나오지 않고, 몇 번이나 찾을 것인가를 함께 봐야 합니다.
딱 한 번만 찾을 것이라면
정리하는 데 드는 노력이 아깝습니다. 그냥 순차 탐색으로 한 번 찾는 편이 나을 수 있습니다.
앞으로 여러 번 찾을 것이라면
데이터가 자주 바뀌지 않는다면, 한 번 정리해 두고 그 뒤로 찾을 때마다 이득을 봅니다. 한 번 들인 노력을 여러 번의 탐색이 나누어 갚는 셈입니다.
도서관이 책을 번호순으로 꽂아 두는 이유가 여기 있습니다. 한 번 꽂아 두는 수고는 크지만, 그 뒤로 수많은 사람이 빠르게 찾아갑니다. 반대로 오늘 하루만 쓰고 버릴 종이 목록이라면 굳이 정리할 이유가 없습니다.
| 이런 상황이면 | 고를 만한 것 | 왜 |
|---|---|---|
| 데이터의 순서가 뒤섞여 있다 | 순차 탐색 | 이진 탐색은 아예 쓸 수 없습니다. |
| 데이터가 몇 개 되지 않는다 | 순차 탐색 | 차이가 크지 않으므로 규칙이 단순한 쪽이 낫습니다. |
| 데이터가 아주 많고 정렬되어 있다 | 이진 탐색 | 확인 횟수가 눈에 띄게 줄어듭니다. |
| 데이터가 자주 들어오고 빠진다 | 검토해야 합니다 | 바뀔 때마다 순서를 다시 맞추는 일이 계속 생깁니다. |
여기서는 열다섯 권을 놓고 손으로 세어 보는 것까지만 합니다. 책이 열다섯 권이 아니라 수십만 권이라면 두 방법의 차이가 어디까지 벌어지는지 궁금해질 텐데, 그것은 세는 기준을 따로 마련해야 답할 수 있는 물음입니다.
더 알아보기
탐색 시뮬레이터의 「비용 비교」 탭에 있는 「개수를 키워 가며 측정한 작업량」 표에서 순차 탐색과 이진 탐색 두 줄을 나란히 보면, 데이터가 8개에서 128개로 늘 때 두 방법의 차이가 어떻게 벌어지는지 볼 수 있습니다.
교실 뒤 게시판에 이름이 뒤섞인 명단이 붙어 있습니다. 오늘 딱 한 사람을 찾으면 되는 상황과, 앞으로 한 달 동안 매일 여러 사람을 찾아야 하는 상황. 두 경우에 같은 선택을 하겠습니까?
핵심 정리
탐색
search
- 여러 데이터 가운데 내가 찾는 것 하나를 집어내는 일
- 컴퓨터는 한 칸씩 물어 가며 찾는다
- 탐색 알고리즘은 결국 묻는 차례를 정하는 일
순차 탐색
sequential search
- 맨 앞부터 하나씩 차례로 확인한다
- 순서가 뒤섞여 있어도 쓸 수 있다
- 없는 값을 찾을 때는 전부 확인해야 한다
이진 탐색
binary search
- 가운데 값과 비교해 범위를 절반씩 줄인다
- 가운데 인덱스 = (앞 + 뒤) ÷ 2, 소수점 아래는 버린다
- 정렬되어 있어야만 쓸 수 있다
고르는 기준
언제 무엇을 쓸까
- 이진 탐색이 언제나 빠른 것은 아니다 — 맨 앞의 값은 순차 탐색이 더 빠르다
- 정렬에도 시간과 노력이 든다 — 탐색 횟수만 비교해서는 답이 나오지 않는다
- 여러 번 찾을수록 정렬에 든 수고를 나누어 갚는다 — 데이터가 자주 바뀌면 따로 검토한다
확인 퀴즈
배운 내용을 확인해 봅시다.
이진 탐색을 쓰기 위해 반드시 갖추어져 있어야 하는 것은?
정렬된 열다섯 칸에서 이진 탐색을 할 때, 범위가 줄어드는 모습으로 옳은 것은?
탐색 방법을 고르는 일에 대한 설명으로 옳지 않은 것은?