[알고리즘] 이분 탐색 알고리즘

이분 탐색 알고리즘 / 파라매트릭 서치 / 투 포인터

브루트 포스, 그리디, DP와 같은 경우에는 쓰이는 상황이 명확하지 않기 때문에 접근 방식에 가까운 알고리즘이라고 할 수 있다. 그래서 알고리즘 문제를 접근할 때 브루트 포스로 해결할 수 있는가, 만약 안된다면 그리디, DP를 생각해볼 수 있다고 언급했었다.

위 3 가지 알고리즘과 달리 이분 탐색, 파라매트릭 서치, 투 포인터는 일반적으로 사용되는 상황이 정해져있다.

이분탐색 알고리즘-> 정렬된 상태에서만 사용 가능

이분탐색 알고리즘은 O(N) 풀이를 O(logN) 풀이로 바꾸어 줄 수 있다. 이분 탐색 알고리즘은 정렬된 배열에서 특정한 원소를 찾는 알고리즘이다.

따라서, 이분 탐색은 정렬이 가능한 상황과 정렬이 되어 있는 상태에서의 사용을 고려해보아야 한다.

파라매트릭 서치 -> 문제의 답이 선형적이어야 가능

문제가 특정 구조를 만족할 때 사용할 수 있는 알고리즘으로, 최대값, 최소값을 구하는 문제를 결정 문제로 바꾸어 푸는 알고리즘이다.

파라매트릭 서치 알고리즘의 구현은 이분 탐색의 로직을 이용한다.

일반적으로 파라매트릭 서치는 최소값의 최대값, 최대값의 최소값을 구할 때 많이 사용한다.

투 포인터 -> 1차원 배열에서 효율적으로 어떤 작업을 할 때 사용 가능

O(N^2) 풀이를 O(N) 풀이로 바꾸어 줄 알고리즘으로 단지 두 개의 포인터=지점을 이용하여 문제를 푸는 알고리즘이다. 따라서 1차원 배열이 나오고, 답의 후보를 효율적으로 탐색해야 할 때 많이 쓰인다.

📌 이분 탐색 알고리즘

선형 탐색 vs 이분 탐색

예를 들어 [1,2,3,4,5,6,7,8,9] 이런 배열이 존재할 때 맨 처음 1부터 맨 마지막 9까지 차례대로 탐색하는 것을 선형 탐색이라고 한다.

그럼 배열의 크기를 N이라고 한다면, 선형 탐색의 시간 복잡도는 O(N)이라고 볼 수 있다.

이분 탐색의 경우 [1,2,3,4,5,6,7,8,9] 이렇게 정렬되어 있는 배열에서 사용할 수 있는데 만약 숫자 7을 탐색하고 싶으면 1 ~ 9 중 가운데 5를 기준으로 왼쪽 오른쪽을 나누어 7은 5보다 크니깐 오른쪽만 탐색하는 것이다.

숫자 5를 기준으로 배열을 나눈다면 [1,2,3,4] / [5] / [6,7,8,9] 이렇게 나눌 수 있는데 7은 5보다 오른쪽에 위치하므로 [6,7,8,9]의 배열에 들어가 다시 원소를 찾는다. 이런 형태로 찾고자 하는 원소가 나올 때까지 가운데 지점을 중심으로 계속 배열을 반으로 나누어 특정 원소를 찾기 때문에 이분 탐색 알고리즘의 시간복잡도는 O(logN)라고 할 수 있다.

🚀 방법 1

array = [0,1,2,3,4,5,6,7]

def binary_search(array, num):
    left = 0
    right = len(array) - 1

    while left <= right:
        mid = (left + right) // 2

        if array[mid] == num:
            return mid
        
        if array[mid] < num:
            left = mid + 1

        if array[mid] > num:
            right = mid - 1

    return -1

print(binary_search(array, 3)) # 3 -> 값이 아니라 인덱스를 반환하는 것

🚀 방법 2

현재 위치 cur과 보폭을 step이라고 하고 cur을 -1, step을 배열의 크기로 지정하면 cur에서 step 만큼 이동했을 때는 맨 마지막 원소가 될 것이다.

step만큼 이동했을 때 값이 찾고자 하는 값보다 크다면 step을 줄여야 한다. step을 줄일 때는 step을 1/2만큼 줄인다. 그리고 step만큼 나아갈 수 있는지 확인하고, 이동했을 때 값이 찾고자 하는 값보다 작다면 cur을 그 장소로 이동한다.

결론은 step이 0이 될 때까지 수행하는데 만약 현재 위치에서 스텝만큼 갔는데 밖으로 벗어나지 않고 현재 위치에서 step만큼 이동했을 때 값이 찾고자 하는 값보다 작거나 같다면 스텝만큼 현재위치를 이동시킨다.

음 당연히 보폭만큼 갔는데 밖으로 나가면 보폭을 줄여야지

만약 스텝만큼 이동했는데 이동했을 때 도착한 값이 찾고자 하는 값보다 크면 너무 앞서 나간 거니깐 스텝의 크기를 반으로 줄인다.

step이 0이 되면 현재 인덱스 cur을 반환하고 알고리즘을 종료한다.

def binary_search2(array, num):
    cur = -1
    step = len(array)

    while step != 0:
        while (cur + step < len(array) and array[cur+step] <= num):
            cur += step
        step //= 2
        
    if arr[cur] == num:
    	return cur
    else:
    	return -1
    
print(binary_search2([1,3,3,4,5,7,9,10,11,13,13,16], 13)) # 10
# 마지막 13이 있는 위치를 반환함

찾는 값 인덱스 아무거나 출력하는 방법 1과 다르게 중복된 원소가 있으면 가장 오른쪽에 있는 인덱스를 반환한다.

👉🏻 정리

방법1, 방법2 모두 단계마다 절반씩 크기가 줄어들기 때문에 시간복잡도는 O(log n)을 만족한다. 여기서 n은 살펴보는 전체 범위의 크기 = 배열의 크기를 의미한다.

이분 탐색은 정렬된 상태로 사용할 수 있고, 선형 자료구조로 이루어져있어야 한다. 리스트나 배열 등 일직선으로 구성되어 있는 자료구조를 의미한다. 그래프나 트리는 비선형 자료구조이다.

따라서, 정렬이 가능한 상황이거나 정렬이 되어 있는 상황이면 이분 탐색을 고려하면 된다.

👉🏻 정렬이 되어 있지 않은 상태에서의 이분탐색

상황 1) 정렬이 되어있지 않은 상태에서 특정한 원소 한 개를 찾을 때

방법 1) 선형 탐색 -> O(N)
방법 2) 정렬 후 이분탐색 -> O(NlogN) + O(logN)
이므로 정렬되어 있지 않을 때 특정한 원소 하나를 찾을 때는 방법 1이 더 유리하다.

상황 2) 정렬이 되어있지 않은 상태에서 특정한 원소 M개를 찾을 때

방법 1) 선형 탐색 -> O(N) O(M) = O(MN)
방법 2) 정렬 후 이분탐색 -> O(NlogN) + O(MlogN) = O(N+M) O(logN)
이므로 상황 2에선 방법 2가 더 유리하다.

🧀 파라매트릭 서치 알고리즘

파라매트릭 서치는 위에서 이분 탐색 알고리즘 방법2와 같이 맨 오른쪽의 인덱스를 반환하는 것이다.

만약, 어떤 문제에서 어떤 숫자 x가 답이 될 수 있나? 에 대한 상황이 나타난다면

방법 1

def parametric_search(arr):
    ret = -1

    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == True:
            left = mid + 1
            ret = mid

        else: 
            right = mid - 1
    return ret

arr = [True,True,True,True,True,True,True,False,False]
print(parametric_search(arr))

방법 2

def parametric_search2(arr):
    cur = -1
    step = len(arr)

    while step != 0:
        while (cur + step < len(arr) and arr[cur + step] == True):
            cur += step
        step //= 2
    
    return cur

arr = [True,True,True,True,True,True,True,False,False]
print(parametric_search2(arr))

step을 초기에 배열의 크기만큼 해놓고 step이 0이 아니면 반복 -> cur + step이 배열을 벗어나지 않고 True가 나올 때까지 cur을 step만큼 증가시킨다. 그리고 step을 벗어나게 되면 step을 1/2로 줄인다. 파라매트릭 서치에서는 방법 1보단 위 방법이 조금 더 직관적임을 알 수 있다.

파라매트릭 서치 알고리즘을 언제 사용하지?

파라매트릭 서치 알고리즘은 이분 탐색을 사용하는 알고리즘이다. 최대값, 최소값을 구하는 문제를 결정 문제로 바꾸어 푸는 알고리즘인데, 그럼 문제에서 파라매트릭 서치 알고리즘을 사용하려면 이러한 결정 문제로 바꾸었을 때 O/X (True/False)의 형태가 연속적으로 나타날 수 있어야 한다.

🍳 문제 풀이

BOJ 2805
여기서 각 나무의 높이는 10억이다. 그렇기 때문에 자를 수 있는 높이의 경우의 수는 10억 * 나무의 수이기 때문에 요구한 시간복잡도를 만족하지 못한다. 그러면 이러한 이유로 인해 브루트 포스적으로는 풀지 못한다.

import sys

input = sys.stdin.readline

# 나무의 수, 가져야 하는 크기
N, M = map(int,input().split())
trees = list(map(int,input().split()))
max_tree = max(trees)

def is_possible(height):
    global trees, M

    res = 0
    for tree in trees:
        if tree > height:
            res += tree - height
    
    return (res >= M)

def parametric_search(trees):
    cur = -1
    step = max_tree

    while step != 0:
        while (cur + step <= max_tree and is_possible(cur + step)):
            cur += step
        step //= 2

    return cur

print(parametric_search(trees))

참고
인프런 - 세계대회 진출자가 알려주는 코딩테스트