Python에서 검색 알고리즘 구현

검색 기능을 구현하는 것은 언제나 쉽지 않지만, 그렇다고 불가능한 일도 아닙니다.

실생활에서 우리는 정해진 규칙 없이 자유롭게 검색합니다. 찾고자 하는 정보가 있을 만한 곳을 짐작하여 찾아보며, 대부분 어떤 패턴을 따르지 않습니다.

그렇다면 프로그래밍 세계에서도 동일한 방식이 가능할까요?

그렇지 않습니다! 프로그램에서 데이터를 검색하려면 특정한 패턴이 필요합니다. 이 글에서는 다양한 검색 패턴을 따르는 여러 알고리즘을 살펴볼 것입니다.

프로그래밍 세계에는 다양한 검색 알고리즘이 존재합니다. 이 글에서는 가장 중요하고 널리 사용되는 알고리즘을 주로 다루고, 나머지 알고리즘은 독자 여러분이 쉽게 학습할 수 있도록 안내할 것입니다.

여기서 검색이란 배열 내 특정 요소를 찾는 과정을 의미합니다.

각 알고리즘을 하나씩 자세히 살펴보겠습니다.

선형 검색

선형 검색 알고리즘은 이름에서 알 수 있듯이 배열의 요소를 순차적으로 탐색하는 방식입니다. 배열의 처음부터 시작하여 원하는 요소를 찾을 때까지 끝까지 탐색합니다. 만약 찾았다면 프로그램 실행을 종료합니다.

이 알고리즘을 더욱 쉽게 이해할 수 있도록 몇 가지 그림을 통해 선형 검색 알고리즘을 설명하겠습니다.

검색 과정을 살펴보면 최악의 경우, 즉 찾고자 하는 요소가 배열의 마지막에 있거나 배열에 없는 경우, 프로그램 실행에 O(n)의 시간이 소요됨을 알 수 있습니다. 알고리즘 분석 시 최악의 경우 시간 복잡도를 고려해야 하므로 선형 검색 알고리즘의 시간 복잡도는 O(n)입니다.

이제 선형 검색 알고리즘의 구현 방법을 살펴보겠습니다.

선형 검색 구현

선형 검색 알고리즘에 대한 이해가 높아졌을 것입니다. 이제 코드를 작성해 볼 차례입니다. 먼저 선형 검색을 구현하는 단계를 살펴본 후, 코딩을 시도해 보겠습니다. 만약 어려움을 느끼더라도 걱정하지 마십시오. 코드 예시를 제공해 드릴 것입니다.

선형 검색 알고리즘을 구현하는 단계는 다음과 같습니다.

• 검색할 요소들을 담은 배열(예: 행운의 숫자)을 초기화합니다.
• 배열, 배열 길이, 검색할 요소를 입력으로 받는 search_element라는 함수를 만듭니다.
• search_element(arr, n, element) 함수 내부:
  • 주어진 배열을 순회합니다.
    • 현재 요소가 찾고자 하는 요소와 일치하는지 확인합니다.
    • 일치한다면 True를 반환합니다.
  • 만약 반복문을 끝까지 순회했는데도 요소를 찾지 못했다면, 해당 요소는 배열에 존재하지 않는다는 의미이므로 False를 반환합니다.
• search_element 함수의 반환 값을 기반으로 결과를 출력합니다.

이제 위 단계를 바탕으로 선형 검색 알고리즘을 구현하는 코드를 작성해 보세요.

선형 검색 알고리즘 구현을 완료했나요? 잘하셨습니다! 이제 아래 제공되는 코드와 비교하여 확인해 보세요.

만약 완료하지 못했다면 걱정하지 마세요. 아래 코드를 참조하여 구현 방법을 익혀보세요. 쉽게 이해할 수 있을 것입니다.

## 검색 함수
def search_element(arr, n, element):

	## 배열을 순회합니다.
	for i in range(n):

		## 현재 요소와 찾고자 하는 요소가 일치하는지 확인합니다.
		if arr[i] == element:
			## 일치하면 True를 반환합니다.
			return True

	## 요소를 찾지 못하면 이 부분에 도달합니다.
	return False

if __name__ == '__main__':
	## 배열, 배열 길이, 찾을 요소를 초기화합니다.
	arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
	n = 10
	element_to_be_searched = 6
	# element_to_be_searched = 11

	if search_element(arr, n, element_to_be_searched):
		print(element_to_be_searched, "을(를) 찾았습니다.")
	else:
		print(element_to_be_searched, "을(를) 찾지 못했습니다.")

배열에 있는 요소로 프로그램을 실행해보고, 다음으로 배열에 없는 요소로도 실행해 보세요.

선형 검색 알고리즘의 시간 복잡도는 O(n)입니다.

다른 검색 패턴을 사용해서 좀 더 효율적으로 만들 수 있을까요?

네, 가능합니다. 함께 알아보겠습니다.

이진 검색

이진 검색 알고리즘은 배열의 중간 요소를 기준으로 탐색 범위를 좁혀나가는 방식입니다. 이 알고리즘은 반드시 정렬된 배열에서만 사용할 수 있습니다.

이진 검색은 배열을 탐색하면서 중간 요소를 확인하고, 만약 찾았다면 프로그램 실행을 종료합니다. 찾지 못했다면, 중간 요소가 찾고자 하는 요소보다 작으면 중간 요소를 기준으로 왼쪽 배열을 탐색 범위에서 제외합니다. 반대로 중간 요소가 찾고자 하는 요소보다 크면 오른쪽 배열을 탐색 범위에서 제외합니다.

이진 검색은 매 반복마다 탐색 영역을 절반씩 줄여나가므로, 선형 검색보다 탐색 횟수가 훨씬 적습니다.

아래 그림들을 통해 이진 검색 알고리즘을 더욱 쉽게 이해할 수 있을 것입니다.

이진 검색 알고리즘의 시간 복잡도는 O(log n)입니다. 탐색 영역이 반복마다 절반씩 줄어들기 때문입니다. 이는 매우 빠른 속도로 탐색 영역이 줄어드는 것을 의미합니다.

이진 검색 구현

먼저 이진 검색 알고리즘 구현 단계를 살펴본 후 코드를 작성해 보겠습니다. 이진 검색 알고리즘을 구현하는 단계는 다음과 같습니다.

• 검색할 요소들을 담은 정렬된 배열(예: 행운의 숫자)을 초기화합니다.
• 정렬된 배열, 배열 길이, 검색할 요소를 입력으로 받는 search_element라는 함수를 만듭니다.
• search_element(sorted_arr, n, element) 함수 내부:
  • 배열 반복을 위한 인덱스 변수 i를 초기화합니다.
  • 탐색 영역을 관리하기 위해 시작 인덱스 start와 끝 인덱스 end를 초기화합니다.
  • i가 배열의 길이보다 작을 때까지 반복합니다.
    • 탐색 영역의 중간 인덱스를 계산합니다. (start + end) // 2
    • 중간 인덱스 요소가 찾고자 하는 요소와 일치하는지 확인합니다.
    • 일치하면 True를 반환합니다.
    • 일치하지 않으면, 중간 인덱스 요소가 찾고자 하는 요소보다 작다면, 탐색 영역의 시작 인덱스를 middle + 1로 이동합니다.
    • 반대로 중간 인덱스 요소가 찾고자 하는 요소보다 크다면, 탐색 영역의 끝 인덱스를 middle - 1로 이동합니다.
    • 인덱스 i를 증가시킵니다.
  • 만약 반복문을 끝까지 순회했는데도 요소를 찾지 못했다면, 해당 요소는 배열에 존재하지 않는다는 의미이므로 False를 반환합니다.
• search_element 함수의 반환 값을 기반으로 결과를 출력합니다.

선형 검색 알고리즘 구현과 유사한 방식으로 코드를 작성해 보세요.

...

코드를 완성하셨나요?

네, 이제 아래 코드를 통해 자신이 작성한 코드와 비교해 보세요. 혹시 못했더라도 걱정하지 마세요. 아래 코드를 통해 구현 방법을 이해하면 됩니다.

## 검색 함수
def search_element(sorted_arr, n, element):

	## 반복을 위한 배열 인덱스
	i = 0

	## 탐색 영역을 추적하기 위한 변수
	## 시작 및 끝 인덱스로 초기화
	start = 0
	end = n - 1

	## 배열을 순회합니다.
	while i < n:
		## 중간 요소의 인덱스를 구합니다.
		middle = (start + end) // 2

		## 중간 요소와 찾고자 하는 요소가 일치하는지 확인합니다.
		if sorted_arr[middle] == element:
			## 요소를 찾았으므로 True를 반환합니다.
			return True
		elif sorted_arr[middle] < element:
			## 탐색 영역의 시작 인덱스를 오른쪽으로 이동합니다.
			start = middle + 1
		else:
			## 탐색 영역의 끝 인덱스를 왼쪽으로 이동합니다.
			end = middle - 1
		i += 1
	return False


if __name__ == '__main__':
	## 배열, 길이, 찾을 요소를 초기화합니다.
	arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
	n = 10
	element_to_be_searched = 9
	# element_to_be_searched = 11

	if search_element(arr, n, element_to_be_searched):
		print(element_to_be_searched, "을(를) 찾았습니다.")
	else:
		print(element_to_be_searched, "을(를) 찾지 못했습니다.")

요소가 존재할 때와 존재하지 않을 때 다양한 경우를 테스트하여 코드를 검증해 보세요.

결론

이진 검색 알고리즘은 선형 검색 알고리즘보다 훨씬 효율적입니다. 이진 검색을 사용하기 위해서는 배열을 정렬해야 하지만, 선형 검색은 정렬되지 않은 배열에서도 사용할 수 있습니다. 정렬 과정에 시간이 소요되지만, 효율적인 정렬 알고리즘을 함께 사용한다면 이진 검색은 매우 강력한 탐색 방법이 될 것입니다.

이제 파이썬에서 가장 널리 사용되는 검색 알고리즘에 대해 잘 이해하게 되었습니다.

다음에는 인기 있는 자체 호스팅 검색 소프트웨어에 대해 알아보도록 하겠습니다.

즐거운 코딩하세요! 🙂🧑‍💻