선형 탐색이란?
어떤 문제를 해결하나요
데이터가 정렬되어 있지 않거나 한 번만 찾을 때가 있습니다. 짧은 이름 목록, 오늘의 주문, 로그의 첫 오류. 언제나 동작하는 가장 단순한 탐색이 필요합니다.
일상 속 비유
선형 탐색은 외투 주머니 줄에서 열쇠를 찾는 것과 같습니다. 첫 주머니, 다음 주머니를 하나씩 확인하고 찾는 즉시 멈춥니다. 마지막 주머니까지 왔다면 열쇠는 거기 없습니다.
for index, value in enumerate(values):🧥 주머니를 차례로 확인if value == target:🔑 여기 열쇠가 있나요?return index✅ 찾음: 그만 찾기return -1❌ 모든 주머니 확인: 없음선형 탐색은 목표를 찾을 때까지 컬렉션의 항목을 차례로 확인하며, 최대 O(n) 단계가 걸리지만 정렬이 필요 없습니다.
선형 탐색은 처음부터 각 항목을 차례로 확인하여 목표값을 찾거나 끝에 도달할 때까지 진행합니다. 데이터를 미리 정렬할 필요가 없습니다.
알고리즘 동작 과정
- 인덱스 0에서 시작합니다.
- 현재 항목을 목표값과 비교합니다.
- 같으면 인덱스를 반환하고, 다르면 다음 항목으로 이동합니다.
- 마지막까지 일치하지 않으면 -1을 반환합니다.
언제 사용하나요?
- 정렬되지 않았거나 작은 컬렉션.
- 먼저 정렬하는 것이 더 비싼 한 번의 탐색.
- 정확한 값만이 아니라 조건에 맞는 첫 항목 찾기.
필요 없는 경우
- 같은 큰 데이터를 여러 번 검색하기: 한 번 정렬하고 이진 탐색을 쓰거나, 집합이나 딕셔너리를 만듭니다.
- 값이 있는지만 확인하기:
target in values가 더 적은 코드로 같은 일을 합니다.
Python의 선형 탐색(linear search) 시각화
O(n)재생 또는 한 단계를 눌러 비교와 데이터 이동 과정을 확인하세요.
예제 코드
def linear_search(values, target):
for index, value in enumerate(values):
if value == target:
return index
return -1
print(linear_search([14, 3, 27, 8, 19], 8))
실행 결과
3
코드 설명
enumerate() 함수는 각 요소의 위치와 값을 함께 줍니다. 찾는 값이 나오면 함수는 바로 그 위치, 여기서는 3을 돌려줍니다. 리스트를 끝까지 봐도 찾지 못하면 -1을 돌려줍니다. 최악의 경우 모든 요소를 확인하므로 복잡도는 O(n)입니다.
값을 변경하고 Python 설치 없이 CodeUtility 온라인 Python 컴파일러에서 실행하세요.
연습 문제
아래 제안을 따라 코드를 바꿔 보세요. 코드를 직접 고치고 결과를 확인하면 읽기만 할 때보다 레슨을 훨씬 잘 이해할 수 있습니다.
- 빈 리스트, 요소가 하나인 리스트, 중복이 있는 리스트로 테스트해 보세요.
- 단계마다 상태를 출력해서 알고리즘이 동작하는 모습을 살펴보세요.
- 요소 100개, 1,000개, 10,000개로 실행 시간을 재고 다른 방법과 비교해 보세요.
자주 하는 실수
반복문 안에서 -1 돌려주기
첫 번째로 안 맞는 항목 뒤에 탐색을 포기합니다.
for index, value in enumerate(values):
if value == target:
return index
return -1
for index, value in enumerate(values):
if value == target:
return index
return -1
이 레슨을 마쳤나요?
학습 완료로 표시하면 진행 상황을 기록할 수 있습니다.
챌린지로 연습하기
이 레슨에서 배운 내용으로 실제 문제를 풀어 보세요. 모든 챌린지는 브라우저에서 실행되며 즉시 테스트와 AI 리뷰를 받을 수 있습니다.
- First Negative Index Find where the first negative number appears. 쉬움
- 배열 최소값 리스트에서 가장 작은 값을 찾으세요. 쉬움