이분 탐색은 여러 알고리즘 종류 중 나를 애먹게 했던 Best 5 (너무 많나?) 안에 들었던 알고리즘이다.
투 포인터니 뭐니 포인터라는 말만 나오면 몸에 경기를 일으키는 나라서.. 문제만 보고 거부감이 들었던 알고리즘이기도 하다.
하지만.. 난 취업을 해야 하고.. 어쩌겠는고 피할 수 없으면 부딪히고 즐겨야지!
해서 저번 주 평일 아침에 매일매일 하는 알고리즘 스터디에서
그 주 알고리즘을 이분 탐색으로 정하고 문제를 풀었다.
근데 웬걸? 신내림을 받은 듯이 이분 탐색의 접근법을 깨우쳐버렸다....(다는 아니지만 어느정도..)
너무 감사한 것.. 그래서 나만의 이분 탐색 접근법을 잊지 않기 위해 블로그에 정리해둔다.
1. 먼저 문제에서 구해야 하는 값이 무엇인지 명확히 알아야 한다.
백준 1072번 - 게임 https://www.acmicpc.net/problem/1072 의 경우
<게임을 최소 몇 번 더 해야 > 라는 문장은 우리가 이분 탐색으로 구해야 할 값이 '게임 횟수'라는 것을 알려주고 있다.
2. 어떤 값으로 이분 탐색을 할 것인지 명확히 알아야 한다. (이분 탐색의 범위를 정해야 한다)
백준 2805번 - 나무자르기 https://www.acmicpc.net/problem/2805 의 경우
우리가 구해야 할 값이 그 뒤에 나오는 <절단기에 설정할 수 있는 높이의 최댓값> 인 것을 알 수 있고, <적어도 M미터의 나무를 집에 가져가기 위해>를 이용해 문제의 값을 구해야 한다는 것을 알 수 있다.
또 절단기에 설정할 수 있는 높이의 범위의 최솟값은 땅, 즉 0이고 범위의 최대는 문제에서 주어진 가장 긴 나무인 것을 생각해낼 수 있다. (쉽게 말해 땅에서 잘라야 가장 많이 가져갈 수 있고 가장 높은 나무의 꼭대기에서 자르면 0m를 가져간다.)
3. 탐색을 해야 하는 범위 값이 리스트 형식으로 들어오지 않는 이상 무조건 상수로 탐색을 한다.
백준 2776번 - 암기왕 https://www.acmicpc.net/problem/2776 의 경우
이분 탐색의 범위가 리스트 형식으로 들어오는 것을 알 수 있다.
이때 꼭 명심해야 할 것! 리스트로 들어오면 꼭 정렬을 해줘야 한다.
이런 경우가 아니면 상수로 이분 탐색을 해주도록 하자..
아니면 메모리 초과가 난다고...
4. 문제에서 요구하는 게 Upper Bound 인지 Lower Bound인지 target == lst[mid]인지 파악해야 한다.
upper bound 와 lower bound를 둘 다 쓸 수 있는 문제
백준 3020 개똥벌레 https://www.acmicpc.net/problem/3020 이다.
input으론 석순과 종유석이 번갈아가면서 나오는데, 나는 이 문제를 풀기 위해 석순과 종유석의 리스트를 각각 만들어 준 다음 마찬가지로 두 리스트를 정렬하였다.
이분 탐색의 범위는 문제에서 제시된 동굴의 높이이고, 동굴의 높이를 하나하나 확인하면서 몇번째 인덱스에서 target 값에 걸리는지 알아내면 되는 문제였다.
석순 리스트 [1,4,3,2,1,2,3,3] 을 정렬해서 석순의 리스트가 [1,1,2,2,3,3,3,4] 가 되었다고 가정하자. 동굴의 높이는 5이다.
여기서 문제! 만약 target의 값이 3이면 우리는 안 부서진 석순을 찾기 위해 몇 번째 인덱스를 반환해줘야 할까?
답은 6번째 인덱스다. 3 높이에서 날아가도 석순을 부수지 않고 날아갈 수 있기 때문에 부술 수 있는 첫 번째 값은 바로 4부터다. 해서 3의 끝인 6을 반환해준다.
여기서 사용해야 할 이분 탐색 알고리즘이 바로 Upper Bound이다.
UpperBound는 타겟값과 같은 값의 마지막 인덱스를 반환해준다.
Upper Bound
def binary_search(lst, target):
left = 0
right = len(lst)
while left <= right:
mid = (left + right) // 2
if lst[mid] <= target:
start = mid + 1
else:
end = mid - 1
return start
종유석의 경우엔 어떠한가?
석순과 똑같이 [1,1,2,2,3,3,3,4]의 종유석 리스트가 있다고 가정하고, 동굴의 높이 또한 5라고 가정하자.
종유석은 천장애 매달려있기 때문에 석순과 다르게 target의 값을 총 높이 - target 으로 설정해줘야 한다.
그리고 석순은 target값 초과인 석순과 부딪혔지만,
종유석은 석순과 다르게 총 높이 - target 값 이상일 때 부딪힌다는 것을 알아야 한다.
(이해가 안된다면 석순과 다르게 종유석은 매달려 있다는 것을 다시 한번 명심하자)
target이 3일 때 종유석의 target은 2가 된다.
이때 target과 부딪히는 첫 번째 인덱스는 바로 3이다.
이 말은 석순의 길이가 2인 값부터 부딪힌다는 것이고
우리는 값이 2인 첫 인덱스를 구해야 한다.
이렇게 원하는 값이 나오는 첫 위치를 찾을 때 LowerBound를 쓴다.
Lower Bound
def binary_search(lst, target):
left = 0
right = len(lst)
while left <= right:
mid = (left + right) // 2
if lst[mid] < target:
start = mid + 1
else:
end = mid - 1
return start
오늘은 여기까지.. 생각난다.. 더 생각나면 추가하겠습니다!
질문 지적 언제나 환영~
그럼 20000
