알고리즘 (탐색)

탐색

정렬은 특정 데이터안에서 내가 원하는 (조건에 맞는) 데이터가 존재하는지를 확인하는 작업을 의미한다.

탐색도 정렬과 마찬가지로 고급 탐색이 있고 기본 탐색이 있다. 일반적으로 가장 쉽게 떠올릴 수 있는 탐색의 방법은 무식하게 처음부터 끝까지 내가 원하는 조건의 데이터가 있는지를 찾는 순차 탐색 의 방법이 있을 것이다. 여기서 살짝 더 머리를 쓴다면 우리가 자주하는 술게임중에서 up&down 게임에서 사용하는 공식 처럼 전체 데이터의 중간을 확인하고 이게 앞에 있는지 뒤에 있는지 확인하여 찾아가는 이진 탐색 의 방법이 있을 것이다.

순차 탐색

순차 탐색은 말 그대로 순서대로 처음부터 끝까지 탐색하여 데이터를 확인하는 방법이다.

def search(data, want):
	for index in data:
    	if index == data:
        	return index

이진 탐색 (정렬된 데이터)

이진 탐색은 저번에 포스팅한 분할 정복 알고리즘에 해당한다.
분할 정복

분할 정복은 상위의 해답을 찾기 위해서 하위 부터 계산해서 올라오는 방식이다.
또한 이진 탐색 또한 분할 정복에 해당하는 알고리즘이기에 재귀용법을 사용하여 구현한다.

def binary_search(data, want):
    print(data)
    if len(data) ==1 and data[0] == want:
        return True
    if len(data) ==1 and data[0] != want:
        return False
    if len(data) == 0:
        return False
    middle = len(data)//2
    if data[middle] > want:
        return binary_search(data[:middle],want)
    if data[middle] < want:
        return binary_search(data[middle:],want)
    if data[middle] == want:
        return True

이진 탐색과 순차 탐색을 비교했을 때 이진 탐색이 더욱 빠르다는 것을 위의 그림을 보면 알 수 있다. 하지만 이진 탐색을 사용하기 위해서는 반드시!!! 반드시!! data가 정렬 되어있어야 한다.