[알고리즘 이론] 이진 탐색(Binary Search)에 대해 알아보자(feat. 파라메트릭 서치)

- Reference
(이코테 2021 강의 몰아보기) 5. 이진 탐색
"이것이 코딩 테스트다 with 파이썬"

[한빛미디어]이것이 취업을 위한 코딩 테스트다 with 파이썬

이코테 나동빈님의 강의와 책을 토대로 공부한 내용을 정리하였습니다.

0. 글 쓰기에 앞서

백준 17179번 케이크 자르기 문제를 풀다가 이진 탐색(이분 탐색)과 파라메트릭 서치에 대한 정리가 필요함을 느꼈다.

이진 탐색과 파라메트릭 서치란 무엇이고 대표적으로 어떠한 문제들이 있는지 알아보자.

 

1. 이진 탐색(이분 탐색)

탐색 알고리즘은 크게 순차 탐색과 이진 탐색으로 나뉜다.

 

순차 탐색이란 리스트 안에 있는 특정 데이터를 찾기 위해 앞에서부터 순서대로 데이터를 확인하는 방법이다.

그리나 순차 탐색은 데이터의 위치에 따라 모든 데이터를 살펴보아야 할 수도 있으므로 시간이 오래 걸린다는 단점이 있다.(시간복잡도 O(n))

 

이진 탐색(이분 탐색)이란 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 확인하는 방법이다. 이진 탐색은 시작점, 끝점, 중간점을 이용해 탐색 범위를 설정하는데 시간복잡도는 O(log(n))으로 순차탐색보다 훨씬 빠르다.

이진 탐색은 보통 1,000만 이상의 값을 처리해야 할 때 접근하면 좋다.

 

이진 탐색(Binary search)과, 순차 탐색(Sequential search)의 동작 예시

파이썬에는 이런 이진탐색을 쉽게 구현 할 수 있는 라이브러리 bisect 라이브러리가 있다.

• bisect_left(a, x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환
• bisect_right(a, x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환

같은 4여도 left 기준으로 하면 index가 2, right 기준으로 하면 index가 4다.

from bisect import bisect_left, bisect_right
a = [1,2,4,4,8]
x = 4

print(bisect_left(a,x))
print(bisect_right(a,x))

## 2
## 4

 

다음은 재귀함수와 반복문을 각각 사용해서 이진탐색 소스코드를 직접 구현해보았다.

# 이진 탐색 소스코드(재귀함수)
def binary_search(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    print(mid)
    if array[mid] == target:
        return mid
    elif array[mid] > target:
        return binary_search(array, target, start, mid-1)
    else:
        return binary_search(array, target, mid+1, end)

n, target = list(map(int,input().split()))

array = list(map(int,input().split()))

result = binary_search(array, target, 0, n-1)
if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result + 1)

# 이진 탐색 소스코드(반복문)
def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1
    return None

n, target = list(map(int,input().split()))

array = list(map(int,input().split()))

result = binary_search(array, target, 0, n-1)

if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result + 1)

"프로그래머들은 이진 검색 알고리즘의 개요를 듣고 나면 그것을 실제로 프로그래밍을 하는 것은 어렵지 않다고 생각한다. 천만에 말씀이다. 내 말이 믿기지 않거든 이 책을 당장 내려놓고, 이진검색 코드를 작성해보라. 지금 당장 진짜로 해보라." - Programming Pearls(Bentley, Jon)

 

사실, 위의 코드와 이론만 보면 이진 탐색은 굉장히 단순하게 느껴질 수도 있다.

그러나 '생각하는 프로그래밍'의 저자 존 벤틀리는 이진 탐색 코드를 제대로 작성한 프로그래머는 10% 내외라 말 할 정도로 실제 문제에서의 구현은 상당히 어려운 작업이다. 또한 파라메트릭 서치와 같은 이진탐색에서 비롯된 문제들의 경우 이진탐색에 대한 완벽한 이해가 없다면 코드 작성이 어려울 것이다.

위의 소스코드는 이진 탐색의 가장 기초적인 알고리즘이므로 해당 코드는 가급적 외워야겠다.

 

2. 파라메트릭 서치

파라메트릭 서치는 전형적인 이분탐색을 활용한 알고리즘이다.

파라메트릭 서치는 쉽게 말해 최적화 문제를 결정 문제(decision problem)로 바꾸어 푸는 것이다.

 

조금 더 자세히 설명해보면, 특정 범위 내에서 어떤 조건을 만족하는 최댓값을 찾으라는 최적화 문제가 있다면, 이진탐색을 이용하여 범위를 좁혀가며 결정 문제로서 해결해 나가는 것이다.

 

예를 하나 들어보자면,

다음과 같은 10개의 데이터가 있다고 생각해보자.

이때 4번째 데이터 이후부터 파란색인 성질을 갖고 있다고 할때,

해결하고자 하는 문제는 "파란색 데이터"라는 특징을 갖는 데이터의 최솟값 즉 "4"를 찾는 것이다.

우선 이진탐색의 알고리즘과 동일하게 전체 데이터에서 중앙값인 5(혹은 6)이 조건을 만족하는지 확인한다.

조건을 만족한다면 최솟값을 구해야하므로 중앙값 5 기준 좌측 데이터만 살펴보면 되고, 만족하지 않는다면 우측 데이터를 살펴보면 된다.

이번엔 1부터 4까지 중에 똑같이 중앙값을 기준으로 조건을 만족하는지 확인하면 된다.

3은 파란색이 아니므로 3 기준 우측 값들을 보면 되고 4는 파란색이므로 해결하고자 했던 "파란색 데이터"라는 특징을 갖는 데이터의 최솟값이 4임을 알 수 있다.

파라메트릭 서치를 사용하려면 위의 예시에서 처럼 조건을 만족하는 값들이 연속적이어야 한다.

연속적이라는 말은 4이상의 숫자들은 모두 파란색인 것 처럼 정답이 A라면 A 이상의 값들은 모두 조건을 만족해야 한다는 뜻이다. (최댓값의 경우 A이하)

 

3. 정리

파라메트릭 서치의 예시문제로는 17179번 케이크 자르기 문제가 있다.

17179번: 케이크 자르기

이 문제에 대한 해설은 조만간 따로 정리해서 포스팅하도록 하겠다.

이진탐색에 대한 자세한 설명은 (이코테 2021 강의 몰아보기) 5. 이진 탐색 및 이것이 코딩 테스트다 with 파이썬 책을 통해 볼 수 있다.

[한빛미디어]이것이 취업을 위한 코딩 테스트다 with 파이썬