점프 탐색

점프 탐색은 차례가 없는 책에서 페이지를 찾는 방법과 같습니다. 한 뭉치씩 앞으로 넘기며 쪽 번호를 힐끗 보다가, 너무 많이 넘겼으면 마지막 뭉치를 한 장씩 되짚어 갑니다. 정렬된 목록에서는 모든 값을 확인하는 것보다 비교가 훨씬 적게 듭니다.

블록으로 나뉜 정렬된 막대 줄. 건너뛴 블록의 마지막 막대는 흐리게, 목표값이 있을 수 있는 블록은 음영으로 표시되어 있다
블록으로 나뉜 정렬된 막대 줄. 건너뛴 블록의 마지막 막대는 흐리게, 목표값이 있을 수 있는 블록은 음영으로 표시되어 있다

핵심 아이디어

정렬된 목록에서는 블록의 마지막 값을 보면 목표값이 그 블록에 있을 수 있는지 알 수 있습니다. 그 값이 목표값보다 작으면 블록 안의 모든 값도 작기 때문입니다. 그래서 안을 들여다볼 필요가 없습니다. 각 블록의 마지막 값을 차례로 확인하며 블록 전체를 건너뛰다가, 목표값보다 작지 않은 값이 나오면 멈춥니다. 그러면 목표값은 그 블록에만 있을 수 있으니, 블록을 처음부터 스캔합니다.

예시

2, 5, 8, 12, 16, 23, 38, 56, 72, 91에서 23을 3개씩의 블록으로 찾아봅시다. 첫 블록은 8로 끝나고 더 작으므로 건너뜁니다. 둘째 블록은 23으로 끝나고 작지 않으므로, 23은 12, 16, 23 안에만 있을 수 있습니다. 이 블록을 스캔하면 12, 16, 그리고 23이 나와 비교 5번 만에 찾습니다. 선형 탐색은 6번, 이진 탐색은 3번이 필요합니다. 40을 찾을 때는 블록의 마지막 값 8, 23, 72를 거쳐 블록 38, 56, 72에 이릅니다. 38은 작고 56은 이미 크므로 40은 없습니다. 이번에도 비교 5번입니다.

왜 √n인가

블록이 m개씩이면 맞는 블록을 찾는 데 최대 약 n/m번, 그 블록을 스캔하는 데 최대 m번의 비교가 듭니다. 길게 몇 번만 점프하면 스캔이 길어지고, 짧게 여러 번 점프하면 점프가 길어집니다. 합 n/m + m은 두 부분이 같은 m = √n에서 가장 작고, 이때 약 2√n입니다. 값 40개라면 블록은 6개씩이고 비교는 최대 13번, 값 100만 개라면 블록은 1,000개씩이고 비교는 약 2,000번입니다.

어디에 쓰이나

이진 탐색은 비교가 더 적어 약 log₂ n번입니다. 하지만 이진 탐색은 목록 곳곳을 오가는 반면, 점프 탐색은 앞으로만 나아가고 뒤로는 한 번, 한 블록의 처음까지만 돌아갑니다. 그래서 테이프에 담긴 데이터나, 뒤로 돌아가기가 느린 연결 구조의 데이터에 유용했습니다. Ben Shneiderman은 1978년에 이를 jump searching이라는 이름으로 설명했습니다. √n개의 블록으로 나누는 같은 아이디어는 흔히 제곱근 분할이라고 불리며, 다른 많은 알고리즘에도 쓰입니다.

벤 슈나이더만(왼쪽)과 캐서린 플레장, 2012년 Webshop. 슈나이더만은 1978년에 점프 탐색을 기술했다.
벤 슈나이더만(왼쪽)과 캐서린 플레장, 2012년 Webshop. 슈나이더만은 1978년에 점프 탐색을 기술했다.

직접 해 보기

앱을 열고 ‘찾을 값’에서 값을 고른 뒤 ‘단계’를 누르세요. 점프할 때마다 블록의 마지막 값이 강조되고, 건너뛴 블록은 흐려지며, 목표값이 있을 수 있는 블록은 스캔하는 동안 음영으로 표시됩니다. 막대 40개에서 ‘점프 크기’를 √n에서 2나 8로 바꾸고 점프와 스캔의 균형이 어떻게 달라지는지 보세요.

자주 묻는 질문

점프 탐색의 시간 복잡도는?

√n개씩의 블록이면 O(√n)이며, 비교는 최대 약 2√n번입니다. 추가 메모리는 O(1)이고, 정렬된 목록이 필요합니다.

점프 탐색과 이진 탐색의 차이는?

이진 탐색은 매번 남은 부분을 절반으로 줄여 약 log₂ n번 비교하지만, 앞뒤로 오갑니다. 점프 탐색은 일정한 간격으로 앞으로 건너뛰고 블록 하나를 스캔하며, 약 2√n번 비교하고, 뒤로는 한 번만 돌아갑니다.

마지막 블록의 스캔에 이진 탐색을 쓸 수 있나요?

네. 블록을 이진 탐색으로 찾으면 스캔이 m번 비교에서 약 log₂ m번으로 줄어듭니다. 점프에는 여전히 n/m번이 들므로, 이때는 블록을 더 크게 하는 편이 낫습니다.

점프 탐색에는 정렬된 목록이 필요한가요?

네. 블록을 건너뛰어도 되는 것은 마지막 값이 작으면 블록 안의 모든 값이 작기 때문입니다. 앱은 정렬되지 않은 목록을 먼저 정렬합니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

점프 탐색 해 보기