이진 탐색(Binary search)
이진 탐색은 정렬된 일련의 값들이 주어지고, 그 값들 중 원하는 값을 찾는 알고리즘이다. 최솟값과 최댓값, 그리고 중간값을 정하여 중간값이 찾으려는 값보다 크면 중간값을 최댓값으로, 중간값이 찾으려는 값보다 작다면 중간값을 최솟값으로 바꾸어 원하는 값을 찾을 때까지 탐색을 반복하는 알고리즘이다.
간단한 예시를 확인해보자.
1부터 9까지 정렬된 리스트([1, 2, 3, 4, 5, 6, 7, 8, 9])가 주어지고 거기서 3을 찾는다고 하면, 그 순서는 다음과 같을 것이다.
1. 우선 최솟값인 1과 최댓값인 9의 중간값인 5를 정하여 이를 3과 비교한다.
2. 5가 3보다 크므로 최댓값을 4(5까지는 체크했으므로 굳이 포함할 필요는 없다)로 정하여 다시 그 중간값인 2와 3을 비교한다.
3. 2가 3보다 작으므로 최솟값을 3(2까지는 체크했으므로)으로 정하여 다시 그 중간값이 3과 3을 비교한다.
4. 일치하므로 탐색 종료
이를 코드로 구현해보면 다음과 같다.
k = 3
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]
min_num = min(numbers)
max_num = max(numbers)
mid_num = (min_num + max_num) // 2
while min_num < max_num:
if mid_num > k:
max_num = mid_num - 1
elif mid_num < k:
min_num = mid_num + 1
else:
break
mid_num = (min_num + max_num) // 2
print(mid_num)Paramatric search
파라매트릭 서치는 '최적화 문제를 결정 문제로 바꾸어 푸는 방법'으로 설명된다. 그리고 그 과정에서 이진 탐색 알고리즘을 활용한다. 그런데 '최적화 문제를 결정 문제로 바꾸는' 것이 무슨 의미일까?
이진 탐색은 '주어진 (정렬된) 값'에서 원하는 값을 찾는 알고리즘이었다. 반면 파라매트릭 서치는 주어진 범위 내에서 원하는 값 혹은 원하는 조건에 맞는 값을 찾아내는 알고리즘이다. 즉, 지금 탐색 중인 값이 원하는 조건에 해당하는지 아닌지, 예 혹은 아니오 형태의 답이 나오는 문제로 바꾸어 푸는 방법이다. 예를 들어 '고기 200g을 자르는 문제'를 '지금 자른 고기의 양이 200g보다 가벼운가?(혹은 무거운가?)'라는 문제로 변환하여 해결하는 것이다.
파라매트릭 서치의 사용 조건
파라매트릭 서치는 이진 탐색과 마찬가지로 시간복잡도에서 상당한 이점을 보이는 강력한 도구이나, 다음의 세 조건을 만족해야만 활용할 수 있다.
- 특정 조건을 만족하는 값(일반적으로 최솟값 혹은 최댓값)을 찾는 형식의 문제이거나 해당 형식의 문제로 변형이 가능한 문제여야 한다.
- 최댓값을 구하는 문제의 경우 어떤 값이 조건을 만족하면 그 값보다 작은 값은 모두 조건을 만족해야 한다(최솟값의 경우 반대로 큰 값은 모두 조건을 만족해야 한다). 그래야만 이진 탐색으로 답을 구할 수 있기 때문이다.
- 답의 범위가 이산적이거나(정수형과 같이) 허용 오차 범위가 있어야 한다. 답이 연속적일 경우 이진 탐색으로는 정확한 값을 구할 수 없기 때문이다.
예시 문제
실제 파라매트릭 서치를 활용한 문제의 예시로 백준의 랜선 자르기 문제를 들 수 있다.
참고 자료
