CS학습
Linear Search: 배열 내 특정 값의 존재 여부 및 위치를 순차적으로 탐색하는 알고리즘
Linear Search는 배열의 처음부터 끝까지 순차적으로 각 요소를 검사하여 목표 값을 찾는 가장 기본적인 탐색 알고리즘입니다. 별도의 자료구조나 전처리 없이 바로 적용 가능하지만, 데이터의 크기가 커질수록 성능이 저하됩니다. 정렬되지 않은 배열에서 특히 유용하게 사용됩니다.
송민성2분 읽기
1. 개념
Linear Search(선형 탐색)는 배열(Array) 또는 리스트(List)와 같은 순차적인 자료구조에서 특정 값(Target Value)의 존재 여부와 그 위치를 확인하는 가장 간단한 탐색 알고리즘입니다.
2. 왜 사용하는가
- 구현 용이성: 다른 복잡한 탐색 알고리즘(이진 탐색 등)에 비해 구현이 매우 간단합니다.
- 정렬 불필요: 입력 데이터가 정렬되어 있을 필요가 없습니다.
- 작은 데이터셋: 데이터셋의 크기가 작을 때는 다른 알고리즘에 비해 성능 차이가 크지 않습니다.
3. 동작 원리
- 배열의 첫 번째 요소부터 시작합니다.
- 현재 요소를 목표 값과 비교합니다.
- 만약 현재 요소가 목표 값과 같다면, 탐색을 종료하고 현재 요소의 인덱스를 반환합니다.
- 목표 값과 같지 않다면, 다음 요소로 이동하여 2번부터 반복합니다.
- 배열의 끝까지 탐색했는데도 목표 값을 찾지 못하면, 목표 값이 배열에 존재하지 않는다고 판단합니다.
4. 코드 예제
python
def linear_search(arr, target):
"""
배열 arr에서 target 값을 찾는 선형 탐색 알고리즘
"""
for i in range(len(arr)):
if arr[i] == target:
return i # target 값의 인덱스 반환
return -1 # target 값이 배열에 없으면 -1 반환
# 사용 예시
my_array = [5, 2, 9, 1, 5, 6]
target_value = 9
result = linear_search(my_array, target_value)
if result != -1:
print(f"Target value {target_value} found at index {result}")
else:
print(f"Target value {target_value} not found in the array")5. 시간 복잡도 또는 성능 특성
- 최선의 경우(Best Case): O(1) – 목표 값이 배열의 첫 번째 요소인 경우
- 평균의 경우(Average Case): O(n) – 목표 값이 배열의 중간쯤에 있는 경우
- 최악의 경우(Worst Case): O(n) – 목표 값이 배열의 마지막 요소이거나 배열에 없는 경우
여기서 n은 배열의 요소 개수를 의미합니다. Linear Search는 데이터의 크기가 커질수록 성능이 선형적으로 저하되는 단점이 있습니다.
6. 실무 사용 사례
- 작은 데이터셋 검색: 데이터셋의 크기가 작고, 검색 빈도가 낮을 때 사용할 수 있습니다.
- 정렬되지 않은 데이터 검색: 정렬 비용이 높거나 정렬이 불필요한 경우 유용합니다.
- 간단한 검색 기능 구현: 복잡한 알고리즘을 적용하기 어려운 간단한 검색 기능 구현에 적합합니다.
7. 주의할 점
- 데이터의 크기가 커질 경우 성능 저하가 심각하므로, 다른 탐색 알고리즘(이진 탐색 등)을 고려해야 합니다.
- 배열의 크기가 매우 큰 경우, 메모리 사용량과 성능을 고려하여 다른 자료구조를 사용하는 것이 좋습니다.
8. 핵심 정리
Linear Search는 구현이 간단하고 정렬된 데이터가 필요 없다는 장점이 있지만, 데이터 크기가 커질수록 성능이 저하된다는 단점이 있습니다. 따라서 데이터의 크기와 검색 빈도를 고려하여 적절한 탐색 알고리즘을 선택해야 합니다.