[Python] 파이썬 검색 알고리즘 구현 (선형검색, 이진검색, 해시검색)

이번 포스팅에서는 파이썬으로 구현 가능한 대표적인 검색 알고리즘들을 소개하고 코드를 포함하여 자세하게 설명하겠습니다.

 

검색 알고리즘

선형 검색(Linear Search)

선형 검색(Linear Search)은 리스트에서 찾고자 하는 값(target)을 찾을 때, 리스트를 처음부터 끝까지 차례대로 탐색하며 검색하는 방법입니다.

선형 검색의 단점은 검색 대상 데이터의 양이 많을 경우, 최악의 경우 모든 데이터를 한번씩 다 비교해야 하기 때문에 검색 속도가 느리다는 것입니다. 하지만, 데이터가 정렬되어 있지 않거나, 정렬된 데이터의 일부를 찾고자 하는 경우에는 다른 검색 알고리즘보다 더 빠른 속도를 보입니다. 선형 검색 알고리즘의 구현 방법은 간단합니다. 리스트에서 target을 찾을 때, 리스트를 처음부터 끝까지 탐색하면서 target과 일치하는 값을 찾으면 해당 값을 반환하고, 리스트 끝까지 찾아도 일치하는 값이 없으면 False를 반환합니다. 

 

코드

def linear_search(lst, target):
	# 리스트를 처음부터 끝까지 순회하며 값을 찾음
    for i in range(len(lst)):
        if lst[i] == target:
        
        	# 찾은 값의 인덱스 반환
            return i
	
    # 값이 없으면 False 반환
    return False

lst는 검색할 리스트, target은 찾고자 하는 값입니다. 코드에서는 리스트의 길이(len)만큼 반복문을 실행하면서 target과 일치하는 값을 찾으면 해당 값의 인덱스를 반환하고, 리스트 끝까지 찾아도 일치하는 값이 없으면 False를 반환합니다.

선형 검색의 시간 복잡도는 O(n) 입니다. 이는 데이터의 양이 많을 경우, 검색 시간이 길어진다는 것을 의미합니다.

 

 

이진 검색(Binary Search)

이진 검색(Binary Search)은 정렬된 리스트에서 특정 값을 찾기 위해 사용하는 알고리즘입니다. 리스트의 중간 값과 찾고자 하는 값 비교를 통해 검색 범위를 반으로 줄여나가면서 값을 찾아나갑니다.

이진 검색의 시간 복잡도는 O(log n)으로, 선형 검색에 비해 매우 효율적입니다. 하지만 리스트가 정렬되어 있어야만 사용 가능한 단점이 있습니다.

 

코드

def binary_search(arr, target):

    # 초기 인덱스 설정
    left, right = 0, len(arr)-1
    
    # left와 right가 교차할 때까지 반복
    while left <= right:
    
     	# 중간 인덱스 계산
        mid = (left+right)//2
        
        # target을 찾으면 인덱스(mid) 반환
        if arr[mid] == target:
            return mid
            
        # target이 중간값보다 크면 왼쪽 부분 배열을 탐색    
        elif arr[mid] < target:
            left = mid+1
            
        # target이 중간값보다 작으면 오른쪽 부분 배열을 탐색    
        else:
            right = mid-1
            
    # 찾지 못한 경우 -1 반환
    return -1

arr는 정렬된 리스트이고, target은 찾고자 하는 값입니다. 검색 범위를 반으로 줄여가면서 값을 찾아나가기 때문에 while문을 사용하며, 검색이 끝날 때까지 리스트의 중간 값을 찾아 비교해가며 범위를 좁혀나가게 됩니다. 이진 검색 알고리즘은 데이터 검색을 빠르게 처리할 수 있는 효율적인 방법 중 하나이며, 정렬된 데이터의 검색에 매우 유용합니다.

 

 

반응형

 

해시 검색(Hash Search)

해시 검색은 키-값 쌍(key-value pair)으로 데이터를 저장하고, 각 키를 해시 함수(hash function)을 통해 고유한 숫자로 변환하여 저장하는 방식으로 검색을 수행합니다. 이를 통해 데이터 검색 속도를 빠르게 할 수 있습니다. 파이썬에서는 dict라는 내장 자료형을 통해 해시 검색을 지원하고 있습니다. dict는 내부적으로 해시 테이블(hash table)을 사용하여 데이터를 저장하고, 검색 시간 복잡도는 O(1) 에 가깝습니다.

 

코드

# dict 생성
dic = {'name': 'Alice', 'age': 25, 'address': 'Seoul'}

# 요소 추가
dic['email'] = 'alice@example.com'

# 요소 삭제
del dic['address']

# 요소 검색
if 'age' in dic:
    print(f"Age: {dic['age']}")
else:
    print("Age not found")

dic라는 dict를 생성하고, 요소를 추가, 삭제, 검색하는 방법을 보여줍니다. in 키워드를 사용하여 요소가 존재하는지 확인할 수 있으며, del 키워드를 사용하여 요소를 삭제할 수 있습니다. 요소를 검색할 때는 인덱싱 연산자( [ ] )를 사용하여 key에 해당하는 값을 가져올 수 있습니다. 

해시 검색은 검색 대상 데이터의 크기가 크거나, 검색 횟수가 많은 경우 유용한 검색 방법입니다. 하지만 해시 함수의 성능에 따라 검색 성능이 크게 달라지므로, 좋은 해시 함수를 선택하는 것이 중요합니다.

 

---

 

[Python] 파이썬 정렬 알고리즘 구현 (선택정렬, 삽입정렬, 퀵정렬, 힙정렬, 버블정렬)

[Python] 파이썬 정렬 알고리즘 구현 (선택정렬, 삽입정렬, 퀵정렬, 힙정렬, 버블정렬)