들어가기 앞서
해당 글은 이분탐색을 공부하며 개인적으로 느낀 점을 정리하는 글입니다. 따라서 부족한 부분이 많을 수 있습니다. 다만, 이분탐색은 이해하기 쉬운 개념에 비해 완벽하게 구현하기 어려운 기법입니다. 이 글은 실용적인 관점에서 이분탐색을 더 잘 사용하고 싶어하시는 분들께 제 고민과 경험을 공유하고자 작성되었습니다. 참고로 해당 글의 예시들은 Python을 사용하여 작성하였습니다.
글에서 소개하는 개념을 이해하기 위해 먼저 백준 온라인 저지에서 해당 문제들을 풀어보실 것을 추천드립니다. 만약 모든 문제를 무난하게 푸실 수 있다면, 이 글은 읽는 게 도움이 되지 않을 수도 있겠네요.
글이 좀 길어질 지도 모르겠습니다.
문제 목록
1. 이분 탐색이란?
이분 탐색은 정렬된 리스트에서 특정한 값을 찾는 알고리즘입니다.
이 알고리즘은 리스트의 중간값을 선택하여 찾고자 하는 값과 비교합니다. 만약 중간값이 찾고자 하는 값보다 크다면 리스트의 왼쪽 절반을 다시 탐색하고, 중간값이 찾고자 하는 값보다 작다면 리스트의 오른쪽 절반을 다시 탐색합니다. 이 과정을 반복하여 값을 찾습니다.
이분 탐색은 리스트의 크기가 크거나 탐색 범위가 넓을 때 유용한 알고리즘입니다.
예를 들어, 1부터 100까지의 숫자 중에서 73을 찾는다면 이분 탐색을 사용하면 최대 7번의 비교만으로 값을 찾을 수 있습니다.
하지만, 리스트의 크기가 작거나 탐색 범위가 좁을 경우에는 선형 탐색(linear search)이 더 효율적입니다.
이분 탐색은 시간 복잡도가 O(log n)으로 매우 빠르기 때문에 대용량의 데이터를 처리할 때 유용합니다.
2. 등장 유형
이분탐색은 O(logn) 안에 수행되기 때문에 굉장히 빠른 탐색 알고리즘 중 하나입니다. 실제 알고리즘 문제에서 이분탐색을 만난다면 그 문제는 다음과 같은 특성을 가지고 있을 가능성이 높습니다.
•
변수의 범위가 제한조건에서 굉장히 넓게 제시되어 있는 문제
•
완전 탐색, dfs 등의 방식으로 해를 구할 수 있는 문제이지만 시간초과가 나는 문제
•
뭔가 정렬이 용이한 문제
이분탐색은 문제 풀이에서 크게 세 가지 유형으로 나눌 수 있습니다.
1.
정렬된 배열에서 특정 수가 있는가?
2.
정렬된 배열에서 특정 수 n이 여러 개 있을 때 , 가장 왼쪽(혹은 오른쪽)에 있는 n의 위치가 어디인가?
3.
TTTTFFFF… 혹은 FFFFTTTT…의 배열에서 첫번째 (혹은 마지막) T나 F의 위치는 어디인가?
첫 번째 유형은 이분탐색의 기본이 되는 쉬운 유형입니다. 두 번째 유형은 흔히 우리가 보편적으로 사용하는 이분탐색 알고리즘으로 파이썬 내장 라이브러리 bisect에서 bisect_left나 bisect_right를 사용하여 해결할 수 있습니다. 구현이 간단하기 때문에 직접 구현하는 경우가 많습니다.
마지막 세 번째 유형이 실전에서 가장 접하기 쉬운 문제로 Parametric search라고도 불립니다. 이분 탐색을 결정 문제로 바꾸어 T(참), F(거짓) 덩어리가 양 쪽에 있는 문제입니다. 사실 1번과 2번도 십중팔구 3번 문제로 바꿔서 풀 수 있기 때문에 Parametric search만 익숙해져도 많은 이분탐색 문제를 해결할 수 있습니다.
다음으로 각각의 유형에 대해 제가 접근하는 방법을 설명드리겠습니다. 후반에는 기회가 된다면 1,2번 유형을 3번 유형으로 바꾸는 방법과 왜 이 방식이 맞을 수 밖에 없는지, 그 정합성에 대해서도 살펴보겠습니다.
앞으로 배열은 정렬되어 있음(monotonically)을 가정하겠습니다.
3. 유형 1. 배열에 원소가 있는가?
쉬운 유형이기 때문에 유형 자체보다 이분탐색을 해결하는 코드 템플릿을 위주로 설명 드리겠습니다. 쉬운 문제를 하나 잡고 설명 드리겠습니다. 백준 1920 수찾기를 먼저 풀고 와서 보시면 더 도움이 될 것 같습니다.
def search(target):
"""
target이 nums 배열에 있으면 True, 없으면 False를 반환
"""
l, r = 0, len(nums)-1
while l <= r:
mid = (l+r)//2
if nums[mid] == target:
return True
elif nums[mid] < target:
l = mid + 1
elif target < nums[mid]:
r = mid - 1
return False
Python
복사
위의 코드는 문제의 핵심이 되는 함수입니다.
이분 탐색은 배열의 인덱스 두 개로 여러 작업을 하는 투포인터 알고리즘의 응용으로 두 개의 포인터 l과 r을 사용합니다. 각각은 배열의 양 끝을 가리키고 있습니다. 두 원소는 배열의 값이 아닌 인덱스를 저장하고 있음에 주의하세요.
1. 초기 탐색 범위 정하기
이분탐색 문제를 풀 때 가장 먼저 결정해야할 것은 l, r이 배열의 원소를 가리키고 있는지, 하나 더 밖을 가리키고있는지입니다. 보통 [l, r]으로 탐색할 지, [l, r)로 탐색할 지, 둘 중 하나로 결정하시면 됩니다. 편의상 [l, r]를 닫힌 범위, [l, r)을 열린 범위라고 부르겠습니다.
위의 경우는 r = len(s)-1로 리스트의 마지막 원소를 가리키므로 닫힌 범위를 탐색하고 있습니다.
2. 종료 조건 정하기
초기 탐색 범위가 정해지면 종료 조건이 자동으로 정해집니다.
# 경우 1: 열린 조건인 경우
while l < r:
...
# 경우 2: 닫힌 조건인 경우:
while l <= r:
...
Python
복사
하나씩 살펴보겠습니다. 예를 들어 루프가 어찌어찌 돌다가 while문 내부 마지막에서 최종적으로 l=7, r=7이 되었다고 생각해보겠습니다. 그러면 다시 while (?) 에 의해 루프를 종료할 지 결정하게 됩니다.
경우 1의 경우 l=r은 l<r 조건에서 False를 반환하기 때문에 루프를 더이상 돌지 않습니다. 따라서 항상 루프가 종료되면 l == r (== 7)이며, [l, l) 혹은 [7, 7)은 빈 배열이기 때문에 모든 범위를 탐색한 것을 알 수 있습니다.
경우 2의 경우 l=r은 l≤r 조건에서 True를 반환하기 때문에 루프가 한 번 더 돌게 됩니다. 저희가 처음 [l, r)를 초기 범위로 잡았기 때문에 l=r인 시점에서 종료되어야 하는데 한 번 더 루프를 돌면서 예상치 못한(정확히 얘기하면 생각하기 귀찮은) 동작을 한 번 더 하게 되는것이죠.
결론은 간단합니다. 처음에 닫힌 범위로 로 잡았으면 l < r로 잡으면 편하고, 열린 범위로 잡았으면 l ≤ r 를 쓰면 편하다는 것입니다.
의심 되시면 닫힌 범위로 잡고 while l < r로 잡고 (혹은 열린 범위와 ≤) 문제를 풀어보세요. while문 안에 추가적인 조건을 넣고 break를 하거나 하는 불필요한 고려사항이 생기고 코드도 길어지는 것을 확인할 수 있을 것입니다. 오히려 이렇게 한 번 고생하는 게 탐색 범위를 줄이는 과정을 이해하는 과정일 수도 있겠네요.
3. mid를 통한 l, r 업데이트 하기
위에서 닫힌 범위와 열린 범위를 구분하는 것과 긴밀하게 연관이 됩니다. 예를 들어 다음과 같은 배열이 있다고 생각해보겠습니다. 지금 찾고자 하는 값, 즉 target은 4이라고 생각해봅시다.
arr = [0, 1, 2, 3, 4, 6, 7, 9] # 0~7번 인덱스의 8개의 원소가 존재
Python
복사
닫힌 범위와 열린 범위를 이해하기 위해 위의 과정을 나눠서 생각해보겠습니다.
# 닫힌 범위
l, r = 0, len(arr)-1 # l=0, r=7
while l < r:
mid = (l+r)//2 # 현재 mid=(0+7)//2 = 3
Python
복사
인덱스: 0 1 2 3 4 5 6 7
배열: [0, 1, 2, 3, 4, 6, 7, 9]
mid: l ^ r
현재 상황: 3 = nums[mid] < target = 4
Python
복사
여기서 자명한 사실은 mid가 가리키는 값이 target보다 작기 때문에 mid의 오른쪽을 탐색해야한다는 것입니다. 이제부터가 헷갈립니다. 그러면 l을 어떻게 업데이트를 해야할까요? 넘어가기 전에 한 번 고민해보세요.
•
주의: nums[mid] target이 아니므로 탐색 범위에서 제외해야합니다.
인덱스: 0 1 2 3 4 5 6 7
배열: [0, 1, 2, 3, 4, 6, 7, 9]
탐색: x [4, 6, 7, 9]
[l, r] l r
Python
복사
단순히 다음 탐색 범위를 위 처럼 그림을 그려 보면 이해하기 편합니다. 열린 범위이든 닫힌 범위이든 l은 항상 닫힌 쪽으로 설정했으므로 l = mid+1입니다. 기억을 더듬어보면 l은 항상 탐색 범위의 내부 왼쪽을 가리켜야하죠?(inclusive, 왼쪽 닫힘)
이제 루프를 돌아 다음 상황이 왔다고 생각해 보겠습니다
인덱스: 0 1 2 3 4 5 6 7
배열: [0, 1, 2, 3, 4, 6, 7, 9]
x x x x [4, 6, 7, 9]
l ^ r
Python
복사
이번에는 ^로 표시된 mid가 6를 가리키고 있습니다. target은 4이므로 반대로 왼쪽을 탐색해야합니다. 아까 그림을 그리면 이해하기 편하다고 말씀 드렸으니, 다시 한 번 그려보겠습니다.
인덱스: 0 1 2 3 4 5 6 7
배열: [0, 1, 2, 3, 4, 6, 7, 9]
x [4, 6, 7, 9]
l x r
닫힌 범위 [4]
열린 범위 [4, )
Python
복사
r을 줄여야할 것 같긴 한데, r=mid일까요? 아니면 r = mid-1일까요? 문제를 간단하게 만드려면 처음 설정한 범위, 즉 열린 범위와 닫힌 범위에 맞춰서 설정해 주면 됩니다.
닫힌 범위의 경우 6은 제외해야하므로 r = mid-1로 설정하면 되고, 열린 범위는 r = mid로 설정하면 mid 특성상 탐색 범위가 자동으로 가능한 탐색 범위 바로 오른쪽을 가리키게 됩니다.
일반적인 경우는 다음과 같습니다.
탐색 범위 [. . . . . . x . . . . . ]
mid ^
다음 탐색 [. . . . . .] # 닫히면 r=mid-1
다음 탐색 [. . . . . . .) # 열리면 r=mid
Python
복사
이후 다음 탐색에서 함수는 target이 존재함을 확인하겠네요.
4. 최종 구현
def search(target):
# 닫힌 범위
l, r = 0, len(nums)-1 # 주의 1: 초기 범위
while l <= r: # 주의 2: 탐색 범위
mid = (l+r)//2
if nums[mid] == target:
return True
elif nums[mid] < target:
l = mid + 1
elif target < nums[mid]:
r = mid - 1 # 주의 3: 업데이트
return False
Python
복사
def search(target):
# 열린 범위
l, r = 0, len(nums) # 주의 1: 초기 범위
while l < r: # 주의 2: 탐색 범위
mid = (l+r)//2
if nums[mid] == target:
return True
elif nums[mid] < target:
l = mid + 1
elif target < nums[mid]:
r = mid # 주의 3: 업데이트
return False
Python
복사
위의 두 코드는 같은 역할을 합니다. 앞서 설명한 닫힌 범위와 열린 범위를 각각 구현한 것에 불과합니다. 위의 코드를 아래 붙여넣기 하면 둘 다 통과가 되는 것을 확인할 수 있으실겁니다.
# 백준 1920 수찾기 정답 코드
import sys
input = sys.stdin.readline
N = int(input())
nums = list(map(int, input().split()))
nums.sort()
def search(target):
... # 열린 범위나 닫힌 범위 중 하나 복붙
K = int(input())
finds = map(int, input().split())
for to_find in finds: # 찾아야할 수들 담아서 찾아보기
print(1 if search(to_find) else 0) # 각각 있으면 1, 아니면 0 출력
Python
복사
2번 유형 이후로는 열린 유형으로 문제를 해결하는 게 편한 경우가 많지만 두 가지 이해하는 게 필수적입니다. 또한 파이썬 내장 라이브러리도 [l, r)로 구현되어있습니다.
추가 문제
4. 유형 2. 배열에 중복된 요소가 있는 경우
사실 유형 1의 경우 쉬운 유형이라 설명이 길 필요는 없었습니다. 하지만 앞서 설명한 개념은 유형2, 3을 해결하기 위한 설명이기도 합니다.
이 유형에서 해결하고자 하는 문제는 배열에 존재하는 target이 여러 개 있다면 그 중 가장 왼쪽이나 오른쪽에 있는 원소의 인덱스를 찾는 것입니다.
index. 0. 1. 2. 3. 4. 5. 6
arr = [1, 1, 3, 7, 7, 7, 9]
왼쪽. ^
오른쪽. ^
Python
복사
만약 위와 같은 배열에서 target=7이라면 정답은 왼쪽의 경우 3, 오른쪽의 경우 5가 되겠습니다.
사실 이 문제는 유형1의 코드에서 단 한 줄만 바꾸면 각각을 해결할 수 있습니다. 한 번 고민해보세요.
정답
target을 찾았을 때 업데이트는 처음에 열린 범위를 정한 대로 해주면 됩니다. 고민할 게 아니라, 그냥 정한 그대로 설정해야합니다. 그래야 논리가 꼬이지 않으니까요. 그리고 저희는 그대로 했을 때 l과 r이 어디를 가리키고 있는지를 외우고, 이를 활용해서 정답을 출력하면 되는 겁니다.
그럼 그대로 했을 때 l, r이 가리키는 곳만 이해하고 외우면 됩니다.
가장 좌측을 찾는 이분탐색
예시를 살펴보겠습니다. 앞으로는 열린 범위를 가정하겠습니다.
# 순회 1
index. 0. 1. 2. 3. 4. 5. 6
arr = [1, 1, 3, 7, 7, 7, 9]
mid l ^ r
Python
복사
더욱 좌측을 탐색해야하므로 r = mid로 업데이트 해 줍니다.
# 순회 2
index. 0. 1. 2. 3. 4. 5. 6
arr = [1, 1, 3, 7, 7, 7, 9]
mid l ^ r
Python
복사
이번엔 우측을 탐색해야겠네요
# 순회 3
index. 0. 1. 2. 3. 4. 5. 6
arr = [1, 1, 3, 7, 7, 7, 9]
mid ^
l r
Python
복사
이번에도 우측을 탐색해야합니다
# 순회 4, 끝
index. 0. 1. 2. 3. 4. 5. 6
arr = [1, 1, 3, 7, 7, 7, 9]
mid r=l
Python
복사
저희의 루프 종료 조건인 l = r에 도달했으므로 함수는 종료되었습니다. 이 때의 l을 이용하여 문제에서 요구하는 정답을 구하면 됩니다. 참고로 종료될 때는 항상 l = r입니다.
닫힌 범위로도 해 보시면 루프 종료 후 l=r+1임을 알 수 있습니다. 이 때는 l을 사용할 지 r을 사용할 지 헷갈릴 수 있습니다. 그래서 그냥 열린 범위를 쓰는 게 편한 경우가 많습니다.
# 좌측 탐색 코드
while l < r:
if nums[mid] == target: # tip 1: target을 찾은 경우 명시적으로 표시
r = mid
elif nums[mid] < target:
l = mid+1
elif nums[mid] > target: # tip 2: else라고 쓰지 말고 명시
r = mid
Python
복사
# 좌측 탐색 코드 2
# 위처럼 푸는 게 좋으나 간단히 한다면
while l < r:
if nums[mid] < target:
l = mid + 1
else:
r = mid
Python
복사
# 파이썬 내장 library bisect에 구현된 bisect_left 함수
# 완전 동일한 로직임을 확인할 수 있다
while lo < hi:
mid = (lo+hi)//2
if a[mid] < x: lo = mid+1
else: hi = mid
return lo
Python
복사
좌측 탐색 직관적으로 이해하기
위의 탐색 과정을 보면 target을 찾으면 해당 값으로 계속 r을 고정합니다. 최종적으로 r은 탐색 도중에 가장 좌측의 target을 가리키고 있습니다. 그리고 마지막 탐색에서 l+=1 되어 l = r이되고, 결과적으로는 l이 가장 왼쪽 target을 가리키게 됩니다. 추가적인 특성은 다음과 같습니다. 고민해 보시고 이해하셔도 좋고, 외워도 쓸만합니다.
•
Fact 1: l은 정렬 상태를 유지하기 위해 target이 삽입되어야 할 index이다.
•
Fact 2: 좌측탐색의 경우 l 값 자체는 배열에서 target 미만인 수의 개수이다
•
Fact 3: 우측탐색의 경우 l 값 자체는 배열에서 target 이하인 수의 개수이다
•
Fact 2 + Fact 3: 우측 탐색의 결과 l과 좌측탐색의 결과 l의 차이는 배열에 존재하는 target 수이다.
우측 탐색
우측 탐색은 탐색 범위에 따라 마지막 target의 오른쪽에 위치합니다(열린 구간). 이건 그림을 몇 번 그리다 보면 이해가 될 것이라 생각하고 생략하도록 하겠습니다. 결론적으로 마지막 원소는 nums[r-1] 혹은 동일하게 nums[l-1]이 되겠네요.
참고로 내장 라이브러리인 bisect의 bisect_right 함수는 r(=l)값을 바로 리턴합니다. nums[r-1]이 가장 우측에 존재하는 원소의 인덱스입니다. 또한 bisect 내부의 bisect라는 함수는 bisect_right의 별칭(alias)입니다.
배열에 target이 없는 경우 (열린 구간)
배열에 target이 없는 경우는 어떻게 할까요? 간단히만 살펴보고 넘어가겠습니다.
1.
배열의 모든 원소가 target보다 큰 경우
a.
좌측 탐색: 항상 r = mid로 업데이트 되고, l=r로 끝나므로 l=r=0
b.
우측 탐색: 항상 r = mid로 업데이트 되고, l=r로 끝나므로 l=r=0
2.
배열의 모든 원소가 target보다 작은 경우
a.
좌측 탐색: 항상 l = mid+1로 업데이트 되고 l=r로 끝나므로 l=r=len(nums)
b.
우측 탐색: 항상 l = mid+1로 업데이트 되고 l=r로 끝나므로 l=r=len(nums)-1
3.
배열에 target이 있는 가? (유형 1)
만약 배열에 원소가 있다면, nums[l] == target으로 확인하면 됩니다 (우측 탐색의 경우 nums[l-1] == target). 하지만 1번과 2번에 의해서 l이나 l-1이 배열 밖을 가리킬 수 있습니다. 이것만 주의해서 문제를 풀면 됩니다.
배열에 target이 없으면 1-b와 2-a는 배열 밖을 가리켜 올바르지 못한 답을 내거나 인덱스 에러를 낼 수 있으므로 배열 내부를 가리키는지 확인해야합니다.
정리
앞서 설명은 길었지만 단 몇 줄의 코드를 위한 이해 과정에 불과합니다. 어려우면 그려보고, 귀찮으면 정리된 내용만 사용하시면 됩니다. 간단히 유형1을 유형 2로 바꿔보고 마무리 하겠습니다. 유형 1에서 푼 백준 1920 수찾기 문제의 유형 2 버젼 코드입니다.
# 좌측 탐색
def search(target, nums=nums):
l, r = 0, len(nums)
while l < r:
mid = (l+r)//2
if nums[mid] == target:
r = mid # 주의 1
elif nums[mid] > target:
r = mid
elif nums[mid] < target:
l = mid+1
return l < len(nums) and nums[l] == target # 주의 2
Python
복사
# 우측 탐색
def search(target, nums=nums):
l, r = 0, len(nums)
while l < r:
mid = (l+r)//2
if nums[mid] == target:
l = mid + 1 # 주의 1
elif nums[mid] > target:
r = mid
elif nums[mid] < target:
l = mid+1
return 0 < l and nums[l-1] == target # 주의 2
Python
복사
5. 유형 3. Parametric Search
Parametric Search 는 정렬된 배열이 필요가 없습니다. 다만, 문제의 조건을 수정하여 가상의 TTTTTTFFFF 혹은 FFFFFTTT… 배열을 구상할 수 있다면 사용하시면 됩니다. 이는 00001111 의 배열로 생각할 수 있으므로 정렬된 배열과 같으니까요. 참고로 T는 True, F는 False입니다.
유형 3은 유형 2와 완전히 동일합니다. 보통 이분 탐색 문제가 어려운 이유는 문제를 재구성 하는 과정이 어려워서이지, 이분탐색이 어려워서가 아닙니다.
Parametric Search 문제 이해하기
가장 먼저 파악해야 할 것은 l, r, 그리고 mid로 탐색할 구간입니다. 보통 문제의 제한 조건에서 엄청나게 넓은 범위를 가지고, 출력해야될 대상입니다. 중요한 사실은 배열의 숫자처럼 미리 정해진 것이 아니라 하나하나 랜덤 박스를 열어야 한다는 것입니다.
문제 해결 순서
1.
먼저 탐색 범위 내부의 값이 FFFFFTTTTT인지, TTTTTFFFFF인지, 그리고 가장 마지막 F를 찾는지, 가장 처음 등장하는 T를 찾는 지 등을 명확히 하고 시작해야합니다.
문제를 재정의하기 나름이기 때문에 상관 없지만, 저희는 FFFFFTTTTT를 가정하겠습니다. 이 경우 0000011111처럼 정렬된 배열이라고 생각할 수도 있습니다. 또한, 가장 처음 등장하는 T를 찾아보겠습니다. 이는 유형 2의 좌측탐색과 동일합니다.
2.
상자깡을 시작합니다.
# 순회 1
인덱스 0 1 2 3 4 5 6 7 8 9 10
탐색 범위: [? ? ? ? ? ? ? ? ? ?]
l ^ r
상자깡 결과:[? ? ? ? ? F ? ? ? ?]
Python
복사
3.
업데이트
이 경우 어떻게 업데이트 해야 할까요? 저희는 열린 범위인 [l, r)를 가정하기로 했습니다. 그리고 좌측 탐색이죠. l = mid+1로 업데이트해서 최초의 T를 찾아봅시다.
# 순회 2
인덱스 0 1 2 3 4 5 6 7 8 9 10
탐색 범위: [? ? ? ? ? F ? ? ? ?]
l ^ r
상자깡 결과:[? ? ? ? ? F ? ? T ?]
Python
복사
T이고, 열린 범위이므로 r = mid로 업데이트하여 탐색 구간을 줄입니다.
# 순회 3
인덱스 0 1 2 3 4 5 6 7 8 9 10
탐색 범위: [? ? ? ? ? F ? ? T ?]
l ^ r
상자깡 결과:[? ? ? ? ? F ? T T ?]
Python
복사
# 순회 4
인덱스 0 1 2 3 4 5 6 7 8 9 10
탐색 범위: [? ? ? ? ? F ? T T ?]
l r
^
상자깡 결과:[? ? ? ? ? F F T T ?]
r=l, 탐색 종료
Python
복사
저희는 상자깡 네 번으로 가장 좌측의 T를 찾았습니다. FFFTTT 로 문제를 재구성 하기만 했는데 말입니다. 만약 상자깡의 비용이 높다면 완전 탐색 시 너무 오래 걸립니다. 적고 나니까 유형 2를 반복만 했다는 생각이 드네요.
정리하면 다음과 같습니다.
•
T나 F를 반환하는 상자깡(시뮬레이션, 탐색, 순회, 기타 등등)함수가 비용이 비싼 경우, 그리고 탐색 범위가 FFFFTTT인 경우 좌측 탐색을 통해 가장 왼쪽 T를 찾을 수 있다.
탐색 범위 정하기
이젠 배열을 탐색하는 것이 아니므로 l과 r을 적절히 정하는 것이 중요합니다. 원리는 단순합니다. l은 탐색이 가능한 제일 좌측, r은 가장 우측 바로 오른쪽입니다. 왜 꼭 이렇게 해야할까요? 문제 상황은 다음과 같습니다.
•
ex 1) 그냥 r=굉장히 큰 수인 경우
◦
mid가 탐색이 불가능한 경우가 생길 수 있습니다. 에러가 나겠죠. 만약 r을 그냥 크게 해도 탐색하는 상자깡 함수가 똑같이 TTTTT를 반환한다면 그냥 크게 해도 됩니다
•
ex 2) 탐색 범위가 전부 F인 경우
◦
조금만 생각해보시면 모든 업데이트가 r=mid이므로 FFFFFFFFFFF인 경우 그냥 초기 설정된 r을 그대로 반환합니다. 그럼 그냥 크니까 설정된 답이 될 수 있을까요? 그냥 이렇게 해도 맞는 경우가 있는데, 운이 좋거나 문제가 특수한 경우일 가능성이 높습니다.
저희는 상자깡의 비용이 비싼 경우 parametric search로 문제를 효율적으로 해결할 수 있음을 확인했습니다. 완전히 이해했다면, 다음 문제들을 살펴보겠습니다.
6. 마치며
부족함이 많은 글입니다. 개선 사항, 추가 내용 요청, 비판 그 어떤 피드백도 환영입니다.