[2주차] 완전 탐색 / 이분 탐색

- 탐색 : 많은 데이터 속에서 원하는 데이터를 찾는 것

- 탐색의 종류

     - 완전탐색

     - 이분탐색

     - 깊이우선탐색

     - 너비우선탐색

     - 문자열 탐색

     - KMP

     - BM

- 완전탐색(Brute Force) : 가능한 모든 경우의 수를 탐색하는 알고리즘

                                   비효율적이지만 모든 경우 따지기 때문에 풀리지 않는 문제 없음

- 완전탐색 구현 방법

1) 반복문 활용

   ex. 8장의 카드 속에서 8번 카드 찾기

def solution(arr):
	for i in range(len(arr)):
    	if arr[i] == 8:
        	return i
    return -1

 

2) 재귀함수 활용

    ex. 8장의 카드 속에서 8번 카드 찾기

def solution(arr, loc):
	if arr[loc] == 8:
    	return loc
    else:
    	return solution(arr, loc+1)

- 이분탐색 : 오름차순으로 정렬된 데이터 중에 특정 값의 위치를 찾는 알고리즘

                 중간의 값을 선택하여 찾고자 하는 값과 비교하며 값을 찾아가는 방법

- 이분탐색 구현 방법

  ex. 8장의 카드 속에서 8번 카드 찾기

def solution(arr):
	left = 0
    right = len(arr)-1
    
    while(left <= right):
    	mid = (left + right) // 2
        
        if arr[mid] == 8:
        	return mid
        elif arr[mid] < 8:
        	left = mid+1
        elif arr[mid] > 8:
        	right = mid-1
            
    return mid