- 목표값
- 비교 중
- 제외됨
- 찾음
선형 탐색
선형 탐색은 값을 찾는 가장 간단한 방법입니다. 처음부터 시작해 값이 나올 때까지 하나씩 차례로 확인합니다. 정렬 여부와 상관없이 어떤 목록에서도 작동합니다. 찾을 값을 고르고, 탐색을 재생하거나 비교를 하나씩 진행하며, 값의 위치나 값이 있는지 없는지에 따라 비용이 어떻게 달라지는지 보세요. ‘재생’을 눌러 탐색을 보거나, ‘단계’와 ‘뒤로’로 비교를 하나씩 진행하세요. 단계 슬라이더를 끌면 원하는 곳으로 이동합니다. 점선은 찾는 값을 나타냅니다. 찾을 값, 막대 개수, 시작 순서를 고르거나 직접 숫자를 입력하세요. ‘첫 일치에서 멈추기’를 끄면 일치하는 값을 모두 찾습니다. 보드를 선택한 상태에서는 화살표 키로 한 단계씩 이동하고, 스페이스 바로 재생과 일시 정지를 하며, Home과 End로 처음과 끝으로 이동합니다.
작동 원리
- 찾을 값, 막대 개수, 시작 순서를 고르세요. 직접 숫자를 입력해도 됩니다.
- ‘재생’을 누르거나, ‘단계’와 ‘뒤로’로 비교를 하나씩 진행하세요. 단계 슬라이더를 끌면 탐색의 원하는 지점으로 이동합니다.
- ‘첫 일치에서 멈추기’를 끄면 모든 값을 확인해 일치하는 값을 모두 찾습니다.
선형 탐색의 원리
첫 번째 값을 목표값과 비교합니다. 같으면 끝입니다. 다르면 두 번째 값, 세 번째 값으로 차례로 넘어갑니다. 일치하는 값 없이 목록 끝에 도달하면 목표값은 목록에 없습니다. 준비할 것은 없습니다. 목록이 정렬되어 있을 필요도 없습니다.
비교 횟수
k번째 값은 비교 k번 만에 찾습니다. 최선의 경우는 목표값이 맨 처음에 있을 때로, 비교 한 번입니다. 최악의 경우는 목표값이 맨 끝에 있거나 없을 때로 n번입니다. 모든 값을 확인한 뒤에야 없다고 확신할 수 있기 때문입니다. 목록에 있는 값이라면 평균 약 (n + 1)/2번입니다. 정렬된 목록에서는 이진 탐색이 훨씬 낫습니다. 비교가 약 log₂ n번으로, 값 40개라면 최대 40번 대신 6번이면 됩니다.
자주 묻는 질문
선형 탐색은 어떻게 작동하나요?
목록의 값을 처음부터 끝까지 하나씩 확인하며, 목표값을 찾거나 값이 다 떨어질 때까지 계속합니다. 순차 탐색이라고도 합니다.
선형 탐색의 시간 복잡도는 얼마인가요?
O(n)입니다. 최악의 경우, 즉 목표값이 맨 끝에 있거나 없을 때 목표값을 n개 값 모두와 비교합니다. 목록에 있는 목표값이라면 평균 약 (n + 1)/2번 비교합니다.
선형 탐색은 언제 쓰면 좋나요?
짧은 목록, 정렬되지 않았고 한두 번만 탐색하는 목록, 그리고 스트림처럼 순서대로만 읽을 수 있는 데이터에 좋습니다. 먼저 정렬해서 이진 탐색을 쓰는 것은 여러 번 탐색할 때만 이득입니다.
없는 값은 왜 비용이 가장 클까요?
선형 탐색에는 일찍 멈추라고 알려 주는 것이 없기 때문입니다. 일치하는 값이 없다는 것은 모든 값을 확인해야만 알 수 있으므로, 목록에 없는 값은 항상 비교가 n번 필요합니다.
내 숫자가 어딘가로 전송되나요?
아니요. 탐색은 브라우저에서 실행되며, 마지막 설정은 이 브라우저의 로컬 저장소에 남습니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
편집기로 이동