이 글에서는 Python의 리스트(list)와 튜플(tuple)에 선형 검색(linear search)을 적용하는 방법을 알아보겠습니다.
선형 검색은 자료 구조의 첫 번째 요소부터 시작하여 마지막 요소까지 순차적으로 탐색하는 가장 기본적인 검색 알고리즘입니다. 찾고자 하는 요소를 발견하면 그 즉시 탐색을 중단합니다.
선형 검색의 동작 원리
선형 검색은 다음과 같은 방식으로 작동합니다.
- 첫 번째 요소부터 검색을 시작합니다.
- 각 요소를 하나씩 순서대로 확인합니다.
- 찾는 값과 일치하는 요소를 만나면 즉시 검색을 종료합니다.
- 끝까지 탐색해도 일치하는 값이 없으면 '찾지 못함'으로 처리합니다.
구현 단계
리스트와 튜플에 선형 검색을 구현하려면 아래 단계를 따르면 됩니다.
- 검색 대상이 될 리스트 또는 튜플과 찾고자 하는 요소를 초기화합니다.
- 리스트나 튜플을 반복(iteration)하면서 각 요소를 확인합니다.
- 요소를 찾으면 반복문을 종료하고 플래그(flag)를 표시합니다.
- 플래그 값을 기준으로 '요소를 찾지 못했다'는 메시지를 출력합니다.
예제 코드
실제 코드로 살펴보겠습니다.
# 선형 검색 함수
def linear_search(iterable, element):
# 상태를 표시할 플래그
is_found = False
# 반복 가능한 객체를 순회하며 탐색
for i in range(len(iterable)):
# 요소 일치 여부 확인
if iterable[i] == element:
# 플래그를 설정하고 결과 메시지 반환
is_found = True
return f"{element} found"
# 요소 존재 여부 최종 확인
if not is_found:
# 찾지 못했다는 메시지 반환
return f"{element} not found"
# 리스트와 튜플 초기화
numbers_list = [1, 2, 3, 4, 5, 6]
numbers_tuple = (1, 2, 3, 4, 5, 6)
print("List:", linear_search(numbers_list, 3))
print("List:", linear_search(numbers_list, 7))
print("Tuple:", linear_search(numbers_tuple, 3))
print("Tuple:", linear_search(numbers_tuple, 7))실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
List: 3 found List: 7 not found Tuple: 3 found Tuple: 7 not found
코드 설명
위 코드의 핵심 로직을 정리하면 다음과 같습니다.
- linear_search 함수: 반복 가능한 객체(iterable)와 찾을 요소(element)를 매개변수로 받습니다.
- is_found 플래그: 요소를 찾았는지 여부를 추적하는 불리언 변수입니다.
- f-string 활용: 찾은 요소의 값을 포함한 메시지를 동적으로 생성하여 반환합니다.
선형 검색의 시간 복잡도는 최악의 경우 O(n)입니다. 즉, 데이터 개수가 많아질수록 검색 시간이 비례해서 늘어납니다. 따라서 소규모 데이터에는 적합하지만, 대용량 데이터에는 이진 검색(binary search) 같은 더 효율적인 알고리즘을 고려하는 것이 좋습니다.
마무리
이번 글에서는 Python의 리스트와 튜플에 선형 검색을 구현하는 방법을 배웠습니다. 선형 검색은 모든 검색 알고리즘의 기초가 되는 개념이므로 확실히 익혀두면 좋습니다. 글에 대해 궁금한 점이 있다면 댓글로 남겨주세요.