[알고리즘] 완전탐색, 이분탐색

01 탐색의 정의

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

웹에서 특정 문자를 가진 문서를 찾거나 신용카드, 버스카드 역시 검색 알고리즘 이용

 

02 탐색의 종류

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

 

03 완전탐색

브루트 포스(brute force)라고도 불리며 컴퓨터의 빠른 계산 성능을 활용하여 가능한 모든 경우의 수를 탐색

장점: 풀리지 않는 문제 없음

단점: 효율정 관점에서 최악

 

04 완전 탐색 구현 방법

01 반복문

 

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

 

02 재귀함수

장점: 다양한 방면에서 활용 가능

단점: 쉽게 무한 루프에 빠짐

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

동적 계획법

백트래킹

탐욕법

 

05 이분 탐색

오름차순으로 정렬된 리스트에서 특정값의 위치를 찾는 알고리즘 중간의 값을 선택하여 찾고자 하는 값과의 크고 작음을 비교

ex) 1~ 100중에 하나 숫자 맞추기

 

이분탐색 : 데이터가 정령돼 있는 배열에서 특정한 값을 찾아내는 것을 이분탐색이라고 합니다. 배열의 중간에 있는 임의의 값을 선액하여 찾고자 하는 값 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