[방학의 PS] 이분 탐색과 매개 변수 탐색 - BOJ_2805, BOJ_1654

자료구조 및 알고리즘을 간략하게나마 공부했던 학생들을 대상으로 한 review 및 관련 문제 풀이 형식의 글입니다.😊

 

1. Binary Search

이분 탐색 또는 이진 탐색은 이미 정렬된 배열에서만 사용할 수 있는 탐색 알고리즘입니다.

우리가 찾으려는  원소를 target이라고 합시다. 그리고 탐색 대상이 되는 배열의 시작을 start, 끝을 end, 가운데에 위치한 원소를 mid라고 합시다.

target < mid 일 경우, 탐색 대상이 되는 배열을 start부터 mid까지 축소합니다. 즉 end = mid가 됩니다.
target > mid 일 경우, 탐색 대상이 되는 배열을 mid부터 end까지 축소합니다. 즉 start = mid가 됩니다.

이렇게 절반씩 뚝뚝 끊어서 탐색하기 때문에 시간 복잡도는 O(log N)이 됩니다.


2. Parametric Search

매개 변수 탐색은 이분 탐색에 최적화 과정을 적용한 알고리즘입니다. 여기서 최적화란 최댓값·최솟값을 찾는 과정을 의미합니다.
즉, 매개 변수 탐색은 이미 정렬된 배열에서 원하는 조건을 만족하는 최댓값 및 최솟값을 이분 탐색을 통해 찾는 탐색 알고리즘입니다.

예를 들면 어떤 오름차순의 배열이 주어졌을 때, '어떤 값보다 큰 가장 작은 원소', 또는 '어떤 값보다 작은 가장 큰 원소'를 찾는 문제에서, 이분 탐색을 활용하여 답을 찾는 경우 이를 매개 변수 탐색이라고 합니다.

이분 탐색을 활용한 알고리즘이기 때문이 마찬가지로 시간 복잡도는 O(log N)이 됩니다.


3. 결론

이분 탐색과 매개 변수 탐색은 단순 탐색에 비해 탐색 시간을 획기적으로 단축해주기 때문에 쓸 수 있다면 상당한 성능의 향상을 보장합니다.

 

---

 

다음은 관련 문제와 제 정답 코드입니다.

 

[1]

https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

풀이 아이디어는 다음과 같습니다.

 

1. 조건이 주어진 최대·최소 문제인지 확인 → 이분 탐색 연상
2. start와 end를 어떻게 설정할 것인가 확인
3. 문제에 주어진 조건을 어떻게 표현할 것인가 확인
4. 탐색을 어떻게 종료할 것인가 확인

k, n = map(int, input().split())
lans = [int(input()) for _ in range(k)]

start, end = 1, max(lans)

while start <= end:
    mid = (start + end) // 2
    lansNum = 0 # 랜선의 수
    for i in lans:
        lansNum += i // mid
    if lansNum >= n:
        start = mid + 1
    else:
        end = mid - 1

print(start)

 

 

---

[2]

https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

n, m = map(int, input().split())
trees = list(map(int, input().split()))

end = max(trees)
start = 0

while start + 1 < end:
    mid = (start + end) // 2
    sum = 0
    for i in trees:
        if (i - mid) > 0:
            sum += (i - mid)

    if sum >= m:
        start = mid
    else:
        end = mid

print(start)