순차 탐색

순차 탐색은 값 목록에서 찾는 값이 어디 있는지 알아냅니다. 맨 앞 값부터 하나씩 차례로 비교하다가 같은 값을 만나면 멈춥니다. 답은 찾은 위치이거나 「없음」입니다. 목록이 정렬돼 있지 않아도 쓸 수 있습니다.

상세

순차 탐색(linear search, sequential search)은 목록에서 값을 찾는 가장 단순한 방법입니다. 선형 탐색이라고도 부릅니다. 목록 속 값을 찾는 방법들을 묶어 탐색 알고리즘이라고 합니다. 순차 탐색은 그 묶음의 출발점입니다.

이 절은 먼저 무엇을 넣고 무엇을 받는지 봅니다. 이어서 절차를 그림과 짧은 파이썬 코드로 따라간 뒤 비교 횟수를 셉니다. 끝으로 이진 탐색 같은 다른 방법과 나란히 놓고 언제 순차 탐색을 고르는지 봅니다. 백엔드 코드에서 이 방법이 숨어 있는 곳도 봅니다.

넣는 것과 받는 것

입력은 둘입니다. 값이 한 줄로 늘어선 목록과 찾을 값 하나입니다.

출력은 찾는 값이 놓인 위치입니다. 위치는 맨 앞을 0번으로 세는 번호입니다. 목록에 그 값이 없으면 「없음」을 돌려줍니다. 코드에서는 흔히 -1 이나 null 이 「없음」을 나타냅니다.

같은 값이 여러 번 들어 있으면 처음 만난 위치를 돌려줍니다. 앞에서부터 보다가 처음 같은 값을 만나는 순간 멈추기 때문입니다.

한 칸씩 비교하는 절차

절차는 한 칸마다 두 가지를 묻습니다. 먼저 목록이 끝났는지 묻습니다. 끝나지 않았으면 지금 값이 찾는 값과 같은지 묻습니다. 아래 그림은 두 물음에서 길이 어떻게 갈리는지 보여 줍니다.

flowchart TD
    A["맨 앞 값에서 시작"] --> B{"목록이 끝났나"}
    B -->|예| C["「없음」을 돌려준다"]
    B -->|아니오| D{"지금 값이 찾는 값과 같나"}
    D -->|예| E["지금 위치를 돌려준다"]
    D -->|아니오| F["다음 값으로 넘어간다"]
    F --> B

그림의 고리가 한 바퀴 돌 때마다 비교가 한 번 일어납니다. 고리를 빠져나오는 길은 둘뿐입니다. 같은 값을 만나거나 목록이 끝나는 것입니다.

아래는 이 절차를 파이썬으로 적은 함수입니다. 목록 xs 와 찾는 값 target 을 받습니다. 찾으면 위치를, 못 찾으면 -1 을 돌려줍니다.

def linear_search(xs, target):
    for i, x in enumerate(xs):
        if x == target:
            return i
    return -1

xs = [7, 3, 9, 3]
linear_search(xs, 9)  # 2
linear_search(xs, 3)  # 1
linear_search(xs, 5)  # -1

enumerate 는 목록의 값을 위치 번호와 짝지어 하나씩 내줍니다. for 문이 끝까지 돌고 빠져나오면 목록이 끝난 것이므로 마지막 줄에서 -1 을 돌려줍니다.

9 는 7, 3 과 다릅니다. 세 번째 비교에서 같아서 위치 2 가 나옵니다. 3 은 두 번 들어 있지만 먼저 만난 위치 1 이 답입니다. 5 는 네 값과 모두 달라서 -1 입니다.

비교 횟수

순차 탐색의 비용은 비교를 몇 번 하느냐로 셉니다. 목록의 값이 n 개일 때 찾는 값이 어디 있느냐에 따라 횟수가 달라집니다. 아래 표는 세 경우를 나눠 적은 것입니다.

평균이 절반쯤인 까닭은 이렇습니다. 찾는 값이 앞에서 k 번째에 있으면 k 번 비교합니다. 1번째부터 n번째까지 고르게 평균을 내면 (n+1)/2 번이 되어 n 의 절반쯤입니다.

입력이 커질 때 드는 일이 어떤 빠르기로 느는지를 적는 표기가 빅오 표기법입니다. 목록 길이가 달라도 알고리즘의 빠르기를 한 줄로 말하려고 씁니다. 드는 일이 n 에 비례해 늘면 O(n) 으로 적습니다.

순차 탐색은 평균과 최악이 O(n) 입니다. 평균도 n 의 절반이라 n 에 비례해 늘기 때문입니다. 목록이 두 배로 길어지면 비교도 두 배로 늡니다.

최선은 맨 앞에서 바로 찾는 경우라 목록 길이와 상관없이 비교 한 번입니다. 이렇게 n 과 상관없이 일정한 양은 O(1) 로 적습니다.

입력 크기에 따라 드는 일의 양을 시간 복잡도라고 부릅니다. 알고리즘에 드는 시간을 입력 크기로 가늠하는 잣대입니다.

드는 메모리의 양은 공간 복잡도라고 부릅니다. 순차 탐색이 비교하는 동안 기억할 것은 지금 위치 하나뿐입니다. 목록을 복사하지 않으므로 추가 메모리는 목록 길이와 상관없이 일정합니다. 공간 복잡도로 적으면 O(1) 입니다.

정렬이 필요 없는 까닭

순차 탐색이 값에 묻는 것은 「찾는 값과 같은가」 하나뿐입니다. 어느 값이 더 큰지는 묻지 않습니다. 그래서 값이 뒤죽박죽 놓여 있어도 답이 맞습니다.

크기를 견줄 방법이 없는 값에도 쓸 수 있습니다. 같은지만 가릴 수 있으면 됩니다. 필드가 여럿인 객체 목록에서 필드가 모두 같은 객체를 찾는 경우가 그렇습니다.

이진 탐색은 사정이 다릅니다. 이진 탐색은 정렬된 목록의 가운데 값과 비교해서 답이 없는 절반을 버립니다. 그러려면 값이 크기 순으로 놓여 있어야 하고 크기를 견줄 수 있어야 합니다. 순차 탐색에는 이 두 전제가 없습니다.

앞에서부터만 갈 수 있는 목록

목록은 메모리에 놓이는 방식에 따라 다룰 수 있는 방법이 갈립니다. 두 가지 목록으로 그 차이를 봅니다.

배열은 값이 메모리에 번호 순으로 붙어서 늘어선 목록입니다. 번호만 알면 어느 칸이든 한 번에 갑니다. 이렇게 아무 칸으로나 바로 가는 것을 임의 접근이라고 합니다.

연결 리스트는 값마다 다음 값이 있는 곳을 적어 두는 목록입니다. 그 적어 둔 곳을 따라가며 값을 잇습니다. 가운데 칸에 가려면 맨 앞부터 차례로 따라가야 합니다. 임의 접근이 안 됩니다.

이진 탐색은 가운데 칸으로 바로 뛰어야 합니다. 연결 리스트에서는 가운데까지 가는 데만 앞에서부터 따라가야 해서 이득이 사라집니다. 순차 탐색은 원래 앞에서부터 한 칸씩 가므로 연결 리스트에서도 비교 횟수가 같습니다.

파일이나 네트워크로 한 줄씩 흘러 들어오는 데이터도 앞에서부터만 읽을 수 있습니다. 이런 입력에서 값을 찾을 때도 순차 탐색을 씁니다.

언제 순차 탐색을 고르나

같은 목록에서 값을 찾는 방법은 순차 탐색 말고도 있습니다. 널리 쓰는 두 방법을 순차 탐색과 나란히 놓고 봅니다. 잣대는 미리 할 일과 한 번 찾는 비용입니다.

첫째는 앞에서 본 이진 탐색입니다. 둘째는 해시테이블입니다. 해시테이블은 값을 계산 한 번으로 저장 칸 번호로 바꿔 둡니다. 찾을 때는 그 칸으로 바로 갑니다.

값을 칸 번호로 바꾸는 이 계산을 해시 함수라고 합니다. 해시테이블에 담으려면 값마다 이 계산을 할 수 있어야 합니다. 아래 표의 「전제」 칸이 이것을 적습니다.

표의 log n 은 n 을 절반씩 몇 번 나눠야 1 이 되는지를 뜻합니다. 이진 탐색은 비교 한 번마다 남은 값을 절반으로 줄이므로 비교 횟수가 이만큼입니다. 값이 백만 개면 약 20번입니다. 순차 탐색은 최악에 백만 번입니다.

표에서 정렬에 드는 O(n log n) 은 값끼리 비교해 정렬하는 방법 가운데 비교가 가장 적은 것들의 비용입니다. n 에 log n 을 곱한 양이라 순차 탐색 한 번의 O(n) 보다 큽니다. 그래서 한 번만 찾을 거라면 정렬부터 하는 것은 손해입니다.

여러 번 찾는다면 계산이 바뀝니다. 미리 할 일은 한 번만 치릅니다. 그 뒤로는 찾을 때마다 비교가 줄어듭니다. 찾는 횟수가 늘수록 이진 탐색이나 해시테이블 쪽의 총비용이 순차 탐색보다 작아집니다.

목록이 자주 바뀔 때도 따져 볼 것이 있습니다. 이진 탐색을 쓰려면 새 값을 넣을 때마다 정렬 순서를 지켜야 합니다. 순차 탐색은 새 값을 끝에 붙이기만 하면 됩니다.

값이 몇 개 안 되는 목록에도 순차 탐색을 흔히 씁니다. n 이 작으면 비교 횟수의 차이도 작습니다. 준비할 것도 없고 코드도 가장 짧습니다.

백엔드 코드에 숨은 순차 탐색

자바 ArrayList 의 indexOf · contains 와 파이썬 리스트의 index · in 은 순차 탐색입니다. 목록을 앞에서부터 훑어서 같은 값을 찾습니다. 한 줄짜리 호출이지만 안에서는 최악에 n 번 비교합니다.

이런 메서드를 반복문 안에서 부르면 비용이 곱해집니다. 바깥 반복이 n 번 돕니다. 그때마다 안에서 n 개짜리 목록을 훑으면 비교가 n² 번쯤 일어납니다. 찾을 값을 해시테이블로 만든 집합(set)에 담아 두면 안쪽 비용이 평균 O(1) 로 줄어듭니다.

데이터베이스도 행을 찾을 때 같은 모양의 일을 합니다. 데이터베이스는 행을 빨리 찾으려고 인덱스를 둡니다. 인덱스는 값에서 그 값을 가진 행으로 바로 가게 미리 만들어 둔 찾아보기입니다.

조건에 쓸 인덱스가 없으면 데이터베이스는 테이블의 행을 처음부터 끝까지 읽으며 조건과 비교합니다. 이 읽기를 풀 테이블 스캔이라고 부릅니다. 모양이 순차 탐색과 같아서 비용도 행 수에 비례해 늡니다.

비교를 덜 하는 손질

기본 절차를 조금 고쳐 비교를 줄이는 방법이 있습니다. 널리 알려진 둘을 봅니다.

첫째는 목록 끝에 찾는 값을 하나 붙여 두는 방법입니다. 그러면 끝에 닿기 전에 반드시 같은 값을 만나므로 「목록이 끝났나」를 매 칸 묻지 않아도 됩니다. 멈춘 위치가 붙여 둔 칸이면 답은 「없음」입니다.

이렇게 끝에 붙여 두는 값을 보초 값(sentinel)이라고 부릅니다. 한 칸마다 묻는 것이 둘에서 하나로 줄어듭니다. 칸을 도는 횟수는 줄지 않아서 여전히 O(n) 입니다.

둘째는 정렬된 목록에서 일찍 멈추는 방법입니다. 목록이 작은 값부터 정렬돼 있으면 찾는 값보다 큰 값을 만난 순간 멈춰도 됩니다. 그 뒤에는 더 큰 값만 있기 때문입니다. 없는 값을 찾을 때 비교가 줄어들지만 최악은 여전히 n 번입니다.

관련 항목

순차 탐색 대신 쓰는 탐색 방법

이진 탐색 · 해시테이블 · 이진 탐색 트리 · 보간 탐색 · 트라이 · 블룸 필터

순차 탐색을 고쳐 비교를 줄인 변형

보초 값 · 자기 조직 리스트 · 점프 탐색 · 지수 탐색

순차 탐색이 훑는 자료구조

배열 · 연결 리스트 · 동적 배열 · 문자열 · 임의 접근

순차 탐색의 비용을 재는 도구

빅오 표기법 · 시간 복잡도 · 공간 복잡도 · 점근 표기법

데이터베이스가 행을 찾는 방법

풀 테이블 스캔 · 인덱스 · B-tree · 해시 인덱스 · 실행 계획

순차 탐색이 속하는 상위 분류

알고리즘 · 탐색 알고리즘 · 완전 탐색