2. 완전탐색/이분탐색

완전탐색(브루트포스) : 가능한 모든 경우의 수를 다 구해서 값을 찾는 것
결과 값이 가장 확실하지만 그만큼 시간이 가장 오래걸리는 탐색방법.
Ex) 반복문 활용, 재귀함수 활용(동적계획법, 백트래킹, 탐욕법)

하나의 방향을 정해서 순서대로 탐색,

python

def solution(trump):
	for i in range(len(trump)):
    	if trump[i]==8: #trump가 8이면 return
        	return i
    return -1

python

# 재귀함수
def solution(trump, loc):
	if trump[i]==8: #8이면 return
    	return i
    else:
    	return solution(trump, loc+1)
	

이분탐색 : 데이터가 **정렬돼 있는 배열**에서 특정한 값을 찾아내는 것
배열의 중간에 있는 임의의 값을 선액하여 찾고자 하는 값 X와 비교를 합니다.
X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우축을 대상으로 다시 탐색을 하면서 해당값을 탐색

Ex) 업다운 게임 (범위를 점차 줄여나가는 게임)

python
#정렬되어있는 상태
def solution(trump):
	left=0
    right=len(trump)-1
    
    while (left<=right):
    	mid=(left+right)//2
        if trump[mid]==8:
        	return mid
        elif trump[mid] < 8: #정답보다 작을 경우 left를 mid+1로
        	left=mid+1
        elif trump[mid] > 8:
        	right=mid-1
   	return mid