이 글에서는 가장 기본적인 탐색 알고리즘 중 하나인 선형 검색(Linear Search)의 개념과 원리를 살펴보고, 파이썬 3.x 버전에서 이를 직접 구현하는 방법까지 단계별로 알아보겠습니다.
선형 검색이란?
선형 검색은 리스트나 배열의 처음부터 끝까지 요소를 하나씩 순차적으로 확인하면서 원하는 값을 찾는 가장 단순한 탐색 방식입니다. 데이터가 정렬되어 있지 않아도 사용할 수 있다는 장점이 있으며, 작은 규모의 데이터에서 효율적으로 동작합니다.
알고리즘 동작 과정
주어진 배열 arr[]의 가장 왼쪽(첫 번째) 요소부터 시작하여, 찾고자 하는 값 x와 배열의 각 요소를 하나씩 차례대로 비교합니다.
x와 일치하는 요소를 발견하면, 해당 요소의 인덱스 값을 반환합니다.
배열의 모든 요소를 확인했는데도 일치하는 값이 없다면, -1을 반환하거나 '요소를 찾지 못했다'는 결과를 알립니다.
아래 그림은 위 접근 방식을 시각적으로 나타낸 것입니다.
파이썬 구현 예제
def linearsearch(arr, x):
for i in range(len(arr)):
if arr[i] == x:
return i
return -1
arr = ['t','u','t','o','r','i','a','l']
x = 'a'
print("element found at index "+str(linearsearch(arr,x)))위 코드에서는 for 반복문을 활용해 리스트를 처음부터 끝까지 선형적으로 스캔합니다. 각 인덱스 위치의 요소가 찾고자 하는 값 x와 일치하는지 확인하고, 일치하는 순간 해당 인덱스를 즉시 반환합니다.
실행 결과
element found at index 6
리스트 ['t','u','t','o','r','i','a','l']에서 문자 'a'는 여섯 번째 위치(인덱스 6)에 존재하므로, 프로그램은 6을 출력합니다. 만약 찾는 값이 리스트에 없었다면 -1이 반환됩니다.
아래 그림은 코드 내 변수들의 범위(scope)를 보여줍니다.
마무리
이번 글에서는 파이썬 3.x 환경에서 선형 검색의 동작 원리와 구현 방법을 살펴보았습니다. 선형 검색은 시간 복잡도가 O(n)으로 데이터 양에 비례해 탐색 시간이 늘어나지만, 구현이 매우 간단하고 정렬되지 않은 데이터에도 적용할 수 있어 알고리즘 학습의 첫걸음으로 적합합니다. 더 큰 데이터셋을 다룰 때는 이진 검색(Binary Search) 같은 더 효율적인 알고리즘과 비교해 보는 것도 좋은 학습 방법입니다.