이진 탐색 및 파라메트릭 서치의 이해 및 적용

코딩 테스트를 공부하면서 이진 탐색를 알고리즘을 학습했다. 먼저 해당 유형을 접해보면서 익숙해지는 과정을 진행했다.

 

백준 문제를 풀면서 파라메트릭 서치 방법을 접할 수 있었고, 어떤 방식으로 이진 탐색과 파라메트릭 서치의 차이점과 예제를 통해 파라메트릭 서치를 문제에 적용해보며 파라메트릭 서치가 무엇인지를 정리하고 공유하고자 한다.

---

# 이진 탐색 - Binary Search

임의의 배열에서 특정 원소를 탐색하기 위해선 배열의 모든 원소를 하나씩 들여다보면 된다.

 

반복문을 통해 배열의 모든 원소를 하나씩 확인하는 방법을 완전 탐색(BruteForce Search)라고 부른다. 

 

완전 탐색은 O(N)의 시간 복잡도를 갖는다. 단순하게 배열의 길이만큼 연산 횟수가 선형적으로 늘어난다.

 

10,000,000개의 원소를 가진 배열에 대해서 완전 탐색을 100번 실시한다면, 연산 횟수는 총 10,000,000,000(백억)으로 일반적인 코딩 테스트 문제의 시간 제약 조건에 의해 Time Out Error가 반환된다.

 

이진 탐색의 시간 복잡도는 O(logN)으로, 완전 탐색 방법에 비해 사용되는 연산을 굉장히 낮출 수 있다.

정렬되어 있는 배열에서민 사용이 가능하며, 탐색 범위를 절반으로 줄여가면서 탐색을 수행한다.

N = 100,000,000(1억)인 배열에서 완전 탐색을 수행하면 약 1억번 연산이 발생하지만, 이진 탐색을 수행하면 log(100,000,000)인 약 27번의 연산을 통해서 원하는 원소를 찾아낼 수 있다.

 

---

이진 탐색 동작 방식

이진 탐색은 대표적인 분할 정복(Divide & Conquer) 알고리즘이다.

 

탐색 과정에서 배열을 좌, 우로 쪼개 배열의 크기를 약 절반으로 줄여간다.

 

주요 아이디어는 "정렬된 배열의 중앙값보다 목표로 하는 값이 크면 오른쪽 배열을 탐색하고, 작다면 왼쪽 배열을 탐색한다"이다.

 

이진 탐색은 탐색하고자하는 범위의 시작점, 끝점, 그리고 중간점을 사용해서 탐색을 실시한다.

이진 탐색의 이해를 돕기 위한 다이어그

 

찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색 과정이다.

 

위의 과정을 start < end 동안 반복하고 만약 start > end 상황이 발생할 경우는 해당 배열에 원소가 존재하지 않는 경우이다.

 

아래는 이진 탐색을 Python 반복문으로 구현한 코드이다.

def binary_search(array, target):
    start = 0
    end = len(array) - 1
    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

---

# 파라메트릭 서치 - Parametric Search

파라메트릭 서치는 이진 탐색과 유사한 탐색 방법으로 보통 최적화 문제에 사용하는데, 최적화 문제를 결정 문제로 바꾸어서 해결한다.

 

대표적인 문제를 통해 설명을 진행한다.

 

2805번: 나무 자르기

백준 2805의 나무 자르기 문제이다.

 

문제의 요구 조건은 다음과 같다.

"나무 길이를 담은 배열이 N개 주어졌을 때 적어도 M미터의 나무를 가져가기 위해 필요한 절단기 높이의 최댓값을 반환"

 

절단기 높이의 최댓값을 반환해야하는 최적화 문제임을 알 수 있고, 문제를 해결하기 위해선 절단기의 높이에 따라 가져갈 수 있는 나무의 개수와 M의 값을 비교해나가야한다. 

 

파라메트릭 방법을 적용하게 된다면, 최적화 문제를 결정 문제로 변환해야한다. 이를 접근하는 방법은 다음과 같다.

 

절단기 높이의 최댓값을 구해라 -> 최적화 문제
현재 절단기 높이로 M개 이상의 나무를 구할 수 있는가 -> 결정 문제

 

후자의 연산을 반복하여 절단기 높이의 최댓값을 계산하는 방법이 파라메트릭 서치 방법이다.

 

문제의 제약 조건을 확인했을 때, 원하는 나무의 길이의 범위는 1 ~ 2,000,000,000(20억), 나무의 수는 1 ~ 1,000,000(백만)이다.

 

절단기 높이를 옮겨가면서 M개 이상의 나무를 구할 수 있는지 없는지를 반복적으로 결정해야하는데, 제약 조건의 범위가 너무 크기 때문에 절단기의 높이를 찾는 방법을 완전 탐색으로 계산할 순 없다.

 

O(log N) 복잡도를 갖는 탐색 알고리즘을 사용해야 이를 계산할 수 있는데, 소스 코드와 함께 이를 설명한다.

 

N, M = map(int, input().split())
trees = list(map(int, input().split()))
start = min(trees) # 절단기 높이 범위의 시작 값
end = max(trees) # 절단기 높이 범위의 끝값
result = 0 # M개의 나무를 자를 수 있는 절단기 높이
while start <= end: # 이진 탐색 수행
    mid = (start + end) // 2 # 중앙값 선언
    mid_count = get_count(trees, mid) # 자른 나무의 총 합을 임의의 get_count(사용자 함수)으로 반환 
    if mid_count < M: # 만약, M개를 달성하지 못하면
        end = mid - 1 # 절단기의 높이를 줄임 
    else: # 만약 달성하면
        result = mid # 현재 높이를 저장
        start = mid + 1  # 더 높은 절단기로 M개의 나무를 얻을 수 있는지 탐색하기 위해 절단기의 높이를 늘림

 

이진탐색을 활용하여 해당 문제를 해결할 수 있다.

 

아이디어는 다음과 같다.

절단기 높이의 범위를 나무의 길이의 최댓값, 최솟값으로 시작하여 각각 end, start 값을 초기화한다.
이후 이진 탐색을 위한 반복을 시작한다.

시작(start), 끝값(end)을 통해 중앙값(mid)을 계산한 후, 절단기의 높이가 mid일 때 얻어지는 나무의 개수를 계산한다(사용자 정의 함수 사용 - get_count ).

이후 반환된 값이 목표값(M)을 달성하지 못했다면, end = mid - 1로 갱신(절단기의 높이를 줄인다.)

달성했다면, 현재 높이를 저장하고 최적화 값을 탐색하기 위해 start = mid + 1로 갱신(절단기의 높이를 늘린다.)

 

기존 이진 탐색은 중앙값이 목표로 하는 값과 일치할 때 끝나는 방식이지만, 해당 문제에서는 이진 탐색을 최적 값을 찾을 수 있게 활용한다.

 

최종적으로 start > end 조건을 만족하여 반복문이 종료될 때까지 반복하고, 가장 마지막으로 M을 담고 있는 값이 절단기 높이의 최댓값이다.

---

# 정리

본인은 위 문제를 처음 접했을 때, 문제를 해결하는 특별한 아이디어가 있는 줄 알고 오랜시간 헤멨다.

이진 탐색을 알고 있었지만 파라메트릭 서치의 개념이 부족해서 결정 문제로 전환하는 접근법을 생각해내지 못했다.

멍청했던 가장 큰 이유중 하나는 문제의 제약 조건인 M의 범위 때문에 20억 범위의 계산을 할 수 있나? 라는 사고 방식에 갖혔던 것 같다.

log2(20억)의 결과

 

log2(2,000,000,000)의 값은 약 31이다.

 

즉, 이진 탐색을 사용하면 단 31번의 연산을 통해서 해당 범위의 탐색이 가능하고 N의 범위가 1 ~ 1,000,000임도 한몫하여 이런 생각에 도달하지 못했다.

 

문제의 제약 조건이 20억정도 되거나 터무늬없다면 O(logN) 알고리즘(이진 탐색)을 생각해내하고, 최적화 문제일 경우 파라메트릭 서치를 생각해내자!

 

대입 시절 수능을 준비할 때 문제만 보고도 이 문제는 어떻게 풀어야하는지, 어떤 공식이 필요한지 등을 떠올린 것처럼 무작정 문제를 읽지만 말고 제약 조건도 유심히 보는 습관을 길러야겠다.

또한, Log 함수의 강력함을 다시금 인지하고 생각없이 문제를 접근하는 습관을 줄여나가야겠다.

 

PS. 더 좋은 접근법이 있으면 알려주시면 감사하겠습니다 :)