탐색 문제

지금 내가 읽고 있는 이 포스트에, 내가 원하는 정보가 있을까?
팀원에게 전달받은 데이터에서 정말로 필요한 요소는 어디에 있을까?

이렇게 원하는 어떤 값을 찾는 문제를 '탐색 문제'라고 얘기한다.

탐색 문제는 매우 일반적이고 전형적인 문제의 형식 중 하나이다.
사실상 모든 프로그래밍에는 탐색 문제가 포함되지 않을까..

이런 탐색 문제를 해결하기 위한 방법,
탐색 문제 해결을 위한 알고리즘은 크게 두가지가 존재한다.

바로 선형 탐색 알고리즘(linear search algorithm)과 이진 탐색 알고리즘(binary search algorithm).

하나하나 살펴보자.

선형 탐색 알고리즘

용의자 A가 도주해 그를 경찰이 쫓고 있다.
신입 경찰 B는 A가 숙박하고 있다는 호텔에 도착했다.
B는 1층부터 꼭대기층까지 순서대로 오르며 그를 찾기로 결정했다.

이렇게 모든 값을 순서대로, 처음부터 끝까지
하나씩 탐색을 진행하는 알고리즘이
선형 탐색 알고리즘(linear search algorithm)이다.

선형 탐색 알고리즘의 예시

def linear(e, datalist):

	cnt = -1
    ans = "None"
    
    for i in datalist:
        if i == e:
            cnt += 1
            ans = cnt
            break
        else:
            cnt += 1
            continue
            
    return ans

linear 함수는 목표값과 어떤 데이터 리스트를 받는다.

그 데이터 리스트에 목표값이 존재한다면 값의 인덱스를,
존재하지 않는다면 None을 리턴한다.

선형 탐색 알고리즘을 구현하기 위해 반복문을 사용했다.

선형 탐색 알고리즘을 사용한 프로그램은
목표값이 주어진 자료에 존재한다면, 그를 놓칠 일은 없을 것이다.

그러나 자료의 양이 방대해진다면 탐색 시간은 너무 길어지고
프로그램은 무거워진다.

신입 B는 호텔의 꼭대기 23층에서 A를 마주하나, 체력을 소진하여 그를 놓치고 만다 ...

이러한 효율성 문제를 해결해줄 수 있는 탐색 알고리즘이 존재한다.

이진 탐색 알고리즘

용의자 A는 도주하는 동안 신발이 발에 맞지 않아 고생했다.
타국에서 건너온 A는 신발가게의 생소한 사이즈 단위에 당황한다.
포위망이 좁혀오고 있기에, 신속히 알맞은 사이즈를 찾아내야 한다.

A는 가장 작은 사이즈부터 모든 사이즈를 다 신어보며
확인해볼 수 있지만, 시간이 한정적이다.

따라서 그는 다음과 같이 결정한다.

A는 먼저 신발가게에 있는 모든 사이즈의 중간에 해당하는
사이즈부터 신어본다.

그의 발에는 작았기에, 이번에는 중간 사이즈와 가장 큰 사이즈 사이
중간에 해당하는 사이즈를 신어본다.

이렇게 중간값부터 시작하여 마치 UP DOWN 게임을 하듯이
가능성을 절반씩 줄여가 목표에 근접해가는 알고리즘을
이진 탐색 알고리즘(binary search algorithm)이라 한다.

A는 신발 사이즈 탐색에 이진 탐색 방식을 취했기에
빠르게 신발을 구매하고 다시 도주할 수 있었다...

문제 해결을 위한 최적의 알고리즘 선택은 결과물의 운명을 좌우한다!