2주차 - 완전탐색/이분탐색

탐색이란?

 : 많은 데이터 속에서 원하는 데이터를 찾는 것.

탐색의 종류

• 완전탐색(Brute Force)
• 이분탐색(이진검색)
• 깊이우선탐색(DFS)
• 너비우선탐색(BFS)
• 문자열탐색
• KMP
• BM

 

트럼프 카드들 중에 8은 어디에?

 

 

1. 완전탐색

• 가능한 모든 경우의 수 탐색하며 값을 찾는 것
• 결과 값이 가장 확실하지만 그만큼 시간이 가장 오래걸리는 탐색방법
• 반복문/재귀함수를 이용해 완전탐색

# 반복문을 이용한 완전탐색
def solution(trump):
	for i in range(len(trump)):
    	if trump[i] == 8:
        	return i
    return -1

# 재귀함수를 이용한 완전탐색
def solution(trump, loc):
	if trump[loc] == 8:
    	return loc
    else:
    	return solution(trump, loc+1)

 

---

2. 이분탐색

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

# 이분탐색 예시코드
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
        elif trump[mid] > 8:
        	right = mid - 1
    return mid