이진탐색 & 이분탐색

이번 포스팅에서는 완전탐색/이분탐색을 정리해 보았습니다.

탐색(검색)이란?

많은 데이터 속에서 원하는 데이터를 찾는 것으로 웹에서 특정 문자를 가진 웹 문서를 찾거나 신용카드나 버스카드 역시 검색 알고리즘을 사용 합니다.

탐색의 종류

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

1.완전탐색

완전탐색 이란?

브루트 포스(Broute Force) 탐색 방법을 완전 탐색이라고 합니다. 가능한 모든 경우의 수를 탐색하는 방법이라서 로직의 효율성 관점에서는 최악의 방법이라 할 수 있습니다. 하지만 완전탐색을 통해서 풀리지 않는 문제는 없다 할 수 있습니다.

완전탐색 구현방법

1. 반목문
2. 재귀함수
   • 동적 계획법
   • 백트래킹
   • 탐욕법

완전탐색 - 반복문

뒤집어진 카드에서 하트8을 찾으려면 무작위로 뒤집을 때 카드가 몇장 되지 않는다면 찾을 수 있겠지만 카드가 100만장이 넘는 다 할때 이미 뒤집은 카드가 어떤 것 인지를 알지 못할 수 있습니다. 이때 앞에서 부터 순차적으로 카드를 뒤집어서 확인 해 봅니다.

이를 Python 코드로 작성하면 다음과 같습니다.

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.이분탐색

이분탐색 이란?

이진검색이라고도 표현하며 오름차순으로 정렬된 리스트에서 특정 값의 위치를 찾는 알고리즘 입니다. 중간의 값을 선택하여 찾고자 하는 값과의 크고 작음을 비교하는 방법입니다.

UPDOWN 게임

1 ~ 1000 까지의 수를 찾을때 기회는 8번이라 하면 처음 질문의 값은 그 중간 값인 500을 얘기 할 수 있을 것 입니다.
UP이 라는 답을 얻었을 때 501 ~ 1000 까지 기회는 7번이 되며 또 그 중간인 750을 얘기하여 범위를 반으로 줄여 나갑니다.
이를 반복하면 범위를 지속적으로 반으로 줄여서 탐색 기회를 줄 일 수 있을 것 입니다.

이분탐색 코드 구현

이분탐색 방법을 Python 코드로 구현하면 다음과 같습니다.

def solutuon(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