선형 탐색
정렬되지 않은 명단에서 이름을 찾을 때 하는 것이 바로 선형 탐색입니다. 맨 위에서 시작해 찾을 때까지 아래로 읽어 내려갑니다. 가장 간단한 탐색이며, 어떤 목록에서도 작동하고, 짧은 목록이라면 대개 이것으로 충분합니다.
기본 아이디어
목표값을 목록의 첫 번째 값과 비교합니다. 같으면 멈춥니다. 목표값은 1번째에 있습니다. 다르면 두 번째 값, 세 번째 값과 차례로 비교합니다. 마지막 값도 일치하지 않으면 목표값은 목록에 없습니다. 목록에 대해 미리 알아야 할 것은 없습니다. 정렬되어 있을 필요가 없고, 값은 같은지 비교할 수 있는 것이면 무엇이든 됩니다.
예시
5, 1, 4, 2, 8에서 4를 찾아봅시다. 5는 4와 같은가요? 아니요. 1은요? 아니요. 4는요? 네. 비교 3번 만에 3번째에서 찾았습니다. 이번에는 같은 목록에서 7을 찾아봅시다. 다섯 값을 모두 확인해도 일치하는 것이 없으므로, 비교 5번 끝에 7은 없다는 답이 나옵니다.
비교 횟수
k번째 값을 찾으려면 비교가 k번 필요합니다. 목표값이 어느 위치에 있을 확률이 모두 같다면 평균 (n + 1)/2번이며, 값 40개라면 20.5번입니다. 없는 값은 항상 n번이 듭니다. 마지막 비교가 끝나야 일치하는 값이 없다는 것이 확실해지기 때문입니다. 따라서 비용은 목록 길이에 비례해 늘어나며, 이를 O(n)으로 씁니다.
더 빠른 탐색에는 순서가 필요하다
선형 탐색은 아무것도 건너뛸 수 없습니다. 정렬되지 않은 목록에서는 어떤 값이든 어디에나 있을 수 있기 때문입니다. 목록이 정렬되어 있으면 비교 한 번으로 같은지 아닌지보다 더 많은 것, 즉 목표값이 어느 쪽에 있는지를 알 수 있습니다. 이진 탐색은 이를 이용해 단계마다 목록을 반으로 줄이며, 비교가 약 log₂ n번, 값 40개라면 최대 6번이면 됩니다. 하지만 정렬에도 시간이 들기 때문에, 한 번만 탐색하는 목록이라면 선형 탐색이 더 나은 경우가 많습니다.
작은 개선
보초(센티넬) 방식은 탐색 전에 목표값을 목록 끝에 넣어 두어, 반복문이 목록의 끝인지 확인할 필요 없이 일치 여부만 검사하게 합니다. 값을 찾을 때마다 한 칸 앞으로, 또는 맨 앞으로 옮기면 자주 찾는 값일수록 점점 빨리 찾게 됩니다. 어느 쪽도 최악의 경우 비교 n번은 바뀌지 않습니다.
직접 해 보기
앱을 열고 ‘찾을 값’에서 값을 고른 뒤 ‘단계’를 누르세요. 점선은 목표값의 높이를 나타내고, 각 값은 확인할 때 강조되고 제외되면 흐려지며, 일치하는 값은 초록색이 됩니다. 목록에 없는 값을 찾으면 전체를 한 번 훑는 과정을 볼 수 있고, ‘첫 일치에서 멈추기’를 끄고 값 종류를 적게 하면 일치하는 값을 여러 개 찾을 수 있습니다.
자주 묻는 질문
선형 탐색의 시간 복잡도는 얼마인가요?
최악과 평균의 경우 O(n), 목표값이 첫 번째 값인 최선의 경우 O(1)입니다. 추가 메모리는 필요 없습니다.
선형 탐색과 이진 탐색은 무엇이 다른가요?
선형 탐색은 모든 값을 차례로 확인하며 어떤 목록에서도 작동합니다. 이진 탐색은 정렬된 목록에서만 작동하지만, 단계마다 목표값이 있을 수 있는 부분을 반으로 줄이므로 최대 n번이 아니라 약 log₂ n번 비교하면 됩니다.
선형 탐색에는 정렬된 목록이 필요한가요?
아니요. 그것이 가장 큰 장점입니다. 정렬된 목록에서는 목표값이 있어야 할 위치를 지나는 순간 멈출 수 있지만, 그래도 이진 탐색보다는 느립니다.
선형 탐색은 어디에 쓰이나요?
목록이 짧거나 정렬되지 않은 곳이라면 어디서나 쓰입니다. 작은 배열에서 항목 찾기, 순서대로만 읽을 수 있는 파일이나 스트림 훑기, 모든 요소가 조건을 만족하는지 확인하기 등입니다. JavaScript의 indexOf, Python의 list.index 같은 많은 라이브러리 함수가 선형 탐색입니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
선형 탐색 해 보기