1. 탐색

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

• 완전탐색
• 이분탐색
• 깊이우선탐색
• 너비우선탐색
• 문자열탐색, KMP, BM 등등..

1) 완전탐색 (Brute Force)

• 컴퓨터의 빠른 계산 능력을 이용하여 가능한 모든 경우의 수를 탐색
• 무조건 답을 구하지만, 효율성이 가장 좋지 않은 알고리즘

예) 카드들이 들어있는 리스트 trump에서 8번 카드를 찾기

(1) 반복문 사용

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

(2) 재귀함수 사용

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

2) 이분탐색 (Binary Search)

• 정렬된 리스트에서 특정 값의 위치를 찾는 알고리즘
• 중간값을 선택하여 찾고자 하는 값보다 큰지 작은지 비교

아까와 같은 카드 8 찾기 - 이분탐색 이용

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