[python] 검색 알고리즘
검색 알고리즘은 특정한 값이나 항목을 찾는 것을 목표로 하는 알고리즘입니다. 컴퓨터 과학에서 검색은 매우 중요한 작업이며 다양한 애플리케이션에서 사용됩니다. 이번 블로그 포스트에서는 몇 가지 일반적인 검색 알고리즘에 대해 알아보겠습니다.
선형 검색 (Linear Search)
선형 검색은 가장 간단하고 직관적인 검색 알고리즘입니다. 이 알고리즘은 리스트나 배열을 처음부터 끝까지 순차적으로 탐색하면서 찾고자 하는 값을 찾을 때까지 진행합니다. 이 알고리즘은 시간 복잡도가 O(n)으로 입력 크기에 비례하여 선형적으로 증가합니다.
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
이진 검색 (Binary Search)
이진 검색은 정렬된 리스트나 배열에서 사용할 수 있는 효율적인 검색 알고리즘입니다. 이 알고리즘은 중간 값을 기준으로 검색 대상과의 비교를 통해 탐색 범위를 반으로 줄여나갑니다. 이진 검색은 입력 크기가 n인 리스트에서 시간 복잡도 O(log n)으로 검색을 수행합니다.
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
해시 검색 (Hash Search)
해시 검색은 해시 함수를 사용하여 데이터를 저장하고 검색하는 알고리즘입니다. 이 알고리즘은 고정된 시간 복잡도 O(1)으로 매우 효율적인 검색을 제공합니다. 해시 검색은 데이터를 해시 테이블에 저장하고, 해시 함수를 이용하여 데이터에 대한 키를 계산한 후 해당 키를 가진 데이터를 찾습니다.
class HashTable:
def __init__(self):
self.table = {}
def hash_function(self, key):
# 해시 함수 구현
return hash(key) % 10
def insert(self, key, value):
index = self.hash_function(key)
self.table[index] = value
def search(self, key):
index = self.hash_function(key)
return self.table.get(index, -1)
마무리
위에서 소개한 선형 검색, 이진 검색, 해시 검색은 일반적으로 사용되는 검색 알고리즘입니다. 각 알고리즘은 다른 특징과 성능을 가지고 있으며 특정한 상황에 따라 선택하여 사용해야 합니다. 앞으로의 블로그 포스트에서는 각 알고리즘에 대해 더 자세히 알아보도록 하겠습니다.
참고 자료: