선형 검색
선형 검색(Linear Search)은 배열이나 리스트와 같은 자료 구조에서 특정 값을 찾는 알고리즘 중 가장 간단한 방법 중 하나이다. 이 알고리즘은 처음부터 끝까지 원소를 하나씩 탐색하며, 원하는 값을 찾을 때까지 계속 탐색한다.
예를 들어, 정수형 배열에서 특정 값을 찾기 위해서는 배열의 첫 번째 원소부터 시작하여, 해당 값이 나타날 때까지 계속해서 탐색한다. 만약 찾는 값이 배열에 없다면, 배열을 끝까지 탐색하게 된다. 이러한 방법을 선형 검색이라고 한다.
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1위 코드에서 arr은 검색할 배열이고, target은 찾으려는 값이다. for 루프를 사용하여 배열의 각 원소를 탐색하며, 찾는 값과 일치하는 원소가 있을 경우 해당 인덱스를 반환한다. 만약 배열에 찾는 값이 없다면 -1을 반환한다.
선형 검색의 시간 복잡도는 최악의 경우 배열의 모든 원소를 탐색해야 하므로 이다. 따라서 배열의 크기가 클수록 선형 검색은 비효율적인 알고리즘이 된다.
보초법
보초법(Search Sentinel, Sentinel Linear Search)은 배열에서 원하는 값을 찾는 알고리즘 중 하나로, 배열의 마지막 인덱스에 원하는 값을 저장해두고, 찾으려는 값을 찾으면 해당 값을 반환하는 검색 알고리즘이다.
일반적으로 배열에서 원하는 값을 찾을 때는 배열을 순회하면서 값을 찾는데, 이때 보초법을 사용하면, 순회 중에 검색할 값이 배열에 존재하지 않아도, 마지막 인덱스에 저장한 보초값을 만나면 순회를 종료할 수 있다. 이는 알고리즘의 실행 속도를 향상시킬 수 있다.
numbers = [2, 7, 1, 9, 8, 3]
def linear_search(arr, x):
n = len(arr)
# 리스트의 마지막 원소를 보초로 설정합니다.
last_element = arr[n - 1]
arr[n - 1] = x
i = 0
# 리스트의 처음부터 마지막 원소까지 차례대로 검색합니다.
while arr[i] != x:
i += 1
# 마지막 원소를 원래대로 되돌립니다.
arr[n - 1] = last_element
# 검색 결과에 따라 해당 원소의 인덱스 또는 -1을 반환합니다.
if i < n - 1 or arr[n - 1] == x:
return i
else:
return -1
result = linear_search(numbers, 9)
print(result) # 3
위 코드에서는 리스트의 마지막 원소를 보초로 설정하고, 검색 중 마지막 원소를 찾으면 바로 검색을 종료할 수 있도록 한다. 마지막 원소를 찾았는지 확인하는 조건문에서 i < n - 1은 마지막 원소를 찾은 경우를 제외하기 위한 것이고, arr[n - 1] == x는 마지막 원소가 찾고자 하는 값인 경우를 처리하기 위한 것이다.
이진 검색
이진 검색(Binary Search)은 정렬된 리스트나 배열에서 특정한 값을 찾는 알고리즘 중 하나이다. 이진 검색은 탐색 범위를 반씩 줄여가면서 찾고자 하는 값과 비교하여, 해당 값이 위치한 구간을 좁혀나가는 방법으로 동작한다.
- 탐색할 리스트의 가운데 원소(mid)를 선택한다.
- mid와 찾고자 하는 값(key)을 비교한다.
key == mid: 탐색을 성공적으로 마친다.
key < mid: 리스트의 왼쪽 반에서 검색을 계속한다.
key > mid: 리스트의 오른쪽 반에서 검색을 계속한다. - 검색할 리스트의 크기가 0이 되거나 key를 찾을 때까지 반복한다.
이진 검색은 보초법에 비해 검색 속도가 빠르며, 검색 대상이 정렬된 리스트인 경우에만 사용 가능하다. 이진 검색은 보통 O(log n)의 시간 복잡도를 가지며, 최악의 경우에도 O(log n)의 시간 복잡도를 보장한다.
def binary_search(arr, key):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == key:
return mid
elif arr[mid] < key:
left = mid + 1
else:
right = mid - 1
return -1위 코드에서는 리스트의 왼쪽 끝(left)과 오른쪽 끝(right)을 설정하고, 반복문에서 탐색 범위를 반씩 줄여나가는 방식으로 동작한다. mid를 계산할 때는 나누기(/) 대신 몫 연산자(//)를 사용하여 소수점 이하를 버린다.
numbers = [1, 2, 3, 5, 7, 9, 11]
result = binary_search(numbers, 7)
print(result) # 43가지 알고리즘의 차이점 정리
1. 선형 검색(Linear Search)
- 리스트의 처음부터 끝까지 차례대로 탐색하는 방법
- 리스트의 크기가 작거나, 값이 랜덤하게 분포되어 있을 경우 유용
- 최악의 경우 O(n)의 시간 복잡도를 가짐
2. 보초법(Sentinel Search)
- 리스트의 끝에 검색하고자 하는 값을 추가하여 검색하는 방법
- 탐색하는 값이 리스트에 없을 때, 모든 리스트 원소에 대한 비교 횟수를 줄일 수 있음
- 최악의 경우 O(n)의 시간 복잡도를 가짐
3. 이진 검색(Binary Search)
- 정렬된 리스트에서 중간 값을 선택하고, 찾고자 하는 값과 비교하여 탐색 범위를 반으로 줄여가는 방법
- 리스트가 정렬되어 있어야 하며, 크기가 큰 경우에 유용
- 최악의 경우 O(log n)의 시간 복잡도를 가짐
