[Python] 이진 탐색 알고리즘의 가장 쉬운 설명

들어가며

이분 탐색을 공부하신다면 알고리즘의 기초적인 부분은 알고 있으시다고 가정하겠습니다(참고로 '이진 탐색 = 이분 탐색'입니다). 빅오 표기법과 버블 정렬을 모르는데 이분 탐색을 공부할 이유는 없으니까요. 이 글은 알고리즘의 가장 기초부터 알려드리는 글이 아니며, 곧 적을 아래의 사전 지식들을 완벽하게는 아니지만 알고 있다고 가정합니다. 알고리즘의 기초 개념부터 천천히 말씀드리는 것이 아닌, 이미 지식은 있지만 코딩 테스트 문제를 막상 잘 풀지 못하는 분이 코딩 테스트에 합격하기 위한 글입니다.

이진 탐색을 배우기 위해 필요한 사전 지식은 다음과 같습니다.

사전 지식

-빅오 표기법

-가장 기본적인 시간 복잡도 계산 방법

-정렬 알고리즘 지식(버블 정렬~퀵 정렬, 병합 정렬 등, 퀵/병합 정렬 구현은 못해도 됨)

-자료구조(리스트, 스택, 힙 등)

-그외 여러 알고리즘 기법들에 대해 구현은 못 해도 개념은 알고 있는 정도(Brute-force 등)

 

이진 탐색

퀵 정렬을 아신다고 가정한다고 말씀드렸으므로, 이진 탐색이 뭔지 최소한 들어는 보셨을 겁니다.

명확하게 이진 탐색이 어떻게 동작하는지, 그래서 이진 탐색이 뭔지 예시로 보여드리겠습니다.

 

예를 들어, 값의 범위가 0~50까지 있고, 17이라는 값을 찾고자 한다면 다음과 같은 방법으로 찾는 알고리즘입니다.

1. 0과 50의 중간값 찾기 : 25

   -> 25는 17보다 큼

2. 0과 25의 중간값 찾기 : 12

   -> 12는 17보다 작음

3. 12와 25의 중간값 찾기 : 18

   -> 18은 17보다 큼

4. 12와 18의 중간값 찾기 : 15

   -> 15는 17보다 작음

5. 15와 18의 중간값 찾기 : 16

   -> 16은 17보다 작음

6. 16과 18의 중간값 찾기 : 17

   -> 17 찾기 완료

 

이렇게 한 번 탐색할 때마다 탐색하는 값의 범위가 절반으로 줄어드는 시간 복잡도를 O(log N)의 시간 복잡도를 갖는다 표현하며, 적절한 계산식 또는 함수로 현재의 값이 정답이 맞는지 판단하는 알고리즘을 이진 탐색 알고리즘이라고 합니다.

 

위에서 들었던 예시를 간단하게 문제로 변환하면 다음과 같습니다.

Q. 0~50 이내의 값을 입력받아 가장 빠르게 찾을 수 있는 횟수를 구하라. (찾을 수 없다면 -1을 반환하라)

잠깐 글 읽는 것을 멈추시고, 제가 말씀드렸던 탐색 순서대로 값을 찾는 알고리즘을 직접 한 번 구현해 보시는 것이 좋을 것 같습니다.

구현에 성공하지 못하더라도, 20~30분 정도 시도해 보고 정답을 보시는 것이 훨씬 좋습니다.

 

 

그럼 바로 코드를 보여드리겠습니다. 코드 아래에 추가로 기술한 설명을 함께 봐주시면 좋을 것 같습니다.

num = int(input())

left = 0 # 범위의 최소
right = 50 # 범위의 최대
count = 0 # 값을 찾기 위해 시도한 횟수
bFind = False

while left <= right:
    count += 1

    mid = (left + right) // 2

    if mid == num:
        print(count)
        bFind = True
        break
    elif mid < num:
        left = mid + 1
    elif mid > num:
        right = mid - 1

if not bFind:
    print(-1)

 

반드시 기억하셔야 합니다. 이진 탐색에서 가장 중요하며 반드시 해야 할 작업은

1. left값과 right값을 설정하는 것

2. 현재 mid에 있는 값이 내가 찾는 정답이 맞는지 확인

입니다. 이 2개만 명확히 설정하시면 많은 문제를 해결할 수 있으며, 더 어려운 문제의 해법 또한 '위 2가지 작업 + a'입니다.

이 문제에 적용하여 풀어서 설명을 드릴게요.

 

1. 시작(left)값과 최댓값(right)값을 설정하는 것

left, right값의 범위는 언제나 정답의 범위입니다. 대부분의 문제에서 이 범위는 해당 문제를 완전히 이해한다면 쉽게 유추할 수 있습니다. 쉬운 문제 몇 개만 풀어보면 감이 오실 거예요.

이 문제에서 정답의 범위는 몇부터 몇까지죠? 바로 0부터 50까지입니다.

그럼 left가 0, right가 50이 되는거예요.

2. 현재 mid에 있는 값이 내가 찾는 정답이 맞는지 확인

해당 문제는 쉬운 문제이기 때문에, 찾고자 하는 값이 17이라면 그저 'if mid == 17'만 해주면 됩니다.

하지만 다른 문제에서는 이를 별도의 식으로 만들거나, 함수를 사용해야 할 수도 있습니다.

 

 

위 두가지 조건에 대해 이해하고 설정하였고, 그에 따른 문제 해법은 다음과 같습니다.

1. left와 right값을 설정하고 중간값을 찾기

2. 중간값이 찾는 값인지 확인

3. 찾거나 탈출 조건을 만족할 때까지 반복

    -> left는 계속 늘리고, right는 계속 줄이기 때문에 left가 right값을 넘어서는 순간이 탈출 조건입니다.

 

여기까지의 해법을 완전히 이해하셨다면, 시간이 걸리더라도 코드를 이해하실 수 있을 거라고 생각합니다.

 

이를 바탕으로 이진탐색 알고리즘을 잘 이해되신다면 좋겠습니다.