탐색 알고리즘

브루트 포스(Brute Force)

Brute(무식한) + Force (힘)

• 브루트 포스는 완전 탐색 알고리즘으로 가능한 모든 경우의 수를 모두 탐색하고 조건에 맞는 결과만 가져온다.

• 무시학게 모두 탐색하여 결과를 찾는 방식이기 때문에 100% 정답을 찾는다.

• 브루트 포스 알고리즘을 설계 할 때, '해가 하나 이상 존재한다'라는 가정을 세우고 모든 영역을 탐색하게 함.

구조에 따른 브루트 포스 종류

선형구조 :

• 순차 탐색

비선형 구조:

• BFS(넓이 우선 탐색)

• DFS(깊이 우선 탐색)

순차 탐색

• 데이터가 담겨있는 리스트를 앞에서부터 하나씩 비교해서 원하는 데이터를 찾는 방법

• 시간 복잡도 O(n)

def sequencial(data_list,search_data):
	for index in range(len(data_list)):
    	if data_list[index] == search_data:
        	return index
    return -1

이진 탐색

• 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법

• 시간 복잡도 : O(logn)

• Divide : 리스트를 두 개의 서브 리스트로 나눈다.

• Comquer

  • 검색할 숫자 (search) > 중간값 이면, 뒷 부분의 서브 리스트에서 검색할 숫자를 찾는다.
  • 검색할 숫자 (search) < 중간값 이면, 앞 부분의 서브 리스트에서 검색할 숫자를 찾는다.

def binary_search(data,search):

    if len(data) == 1 and search == data[0]:
	return True
    if len(data) == 1 and search != data[0]:
    	return False
    if len(data) == 0
    	return False
        
    medium = len(data) // 2
    
    if search == data[medium]:
    	return True
    else:
    	if search > data[medium]:
        	return binary_search(data[medium:],search)
        else:
        	return binary_search(data[:medium],search)