Hyem.log

[Algorithm] 완전탐색/이분탐색

July 30, 2021

탐색

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

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

완전탐색 (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)
  • 정렬된 리스트에서 특정 값의 위치를 찾는 알고리즘
  • 중간값을 선택하여 찾고자 하는 값보다 큰지 작은지 비교

✅ 아까와 같은 카드 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
Written by@[hyem]
Hyem's Dev Note

GitHub