📌 "이분탐색 기법을 이용해 효율적으로 값을 찾아보세요"
출제빈도 : 낮음
평균점수 : 낮음
정렬된 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
❗데이터가 모두 정렬되어 있어야만 사용할 수 있다.
찾으려는 데이터(target
)와 탐색범위([start, end]
)의 중간에 위치한 데이터(mid
)를 반복적으로 비교해서 원하는 데이터를 찾는다.
시간복잡도 : O(logN)
[start, end]
)의 중간값(mid
)을 선택해서 찾고자 하는 값(target
)과 일치하는지 확인한다.if mid == target
: 해당값을 반환한다.if mid < target
: 탐색범위를 큰 쪽으로 잡는다. (start = mid + 1
)if mid > target
: 탐색범위를 작은 쪽으로 잡는다. (end = mid - 1
)if start > end
) 종료한다.target = 25
search_list = [30, 94, 27, 92, 21, 37, 25, 47, 25, 53, 98, 19, 32, 32, 7]
search_list.sort()
start = 0
end = len(search_list)-1
while start <= end:
mid = (start + end) // 2
if search_list[mid] == target:
print(mid)
break
elif search_list[mid] > target:
end = mid - 1
else:
start = mid + 1
3 # [7, 19, 21, "25", 25, 27, 30, 32, ... ]
def binary_search(array, target, start, end):
mid = (start + end) // 2
if target == array[mid]:
print(mid)
elif array[mid] > target:
binary_search(array, target, start, mid - 1)
elif array[mid] < target:
binary_search(array, target, mid + 1, end)
else:
return False
target = 25
search_list = [30, 94, 27, 92, 21, 37, 25, 47, 25, 53, 98, 19, 32, 32, 7]
search_list.sort()
start = 0
end = len(search_list)-1
binary_search(search_list, target, start, end)
3 # [7, 19, 21, "25", 25, 27, 30, 32, ... ]
import bisect
bisect_left(정렬된 리스트, 타겟)
: 정렬된 리스트에서 타겟을 삽입할때 들어갈 수 있는 가장 왼쪽 인덱스bisect_right(정렬된 리스트, 타겟)
: 정렬된 리스트에서 타겟을 삽입할때 들어갈 수 있는 가장 오른쪽 인덱스import bisect
target = 25
search_list = [30, 94, 27, 92, 21, 37, 25, 47, 25, 53, 98, 19, 32, 32, 7]
search_list.sort()
print(bisect.bisect_left(search_list, target))
print(bisect.bisect_right(search_list, target))
3 # [7, 19, 21, (여기), 25, 25, 27, 30, 32, ... ]
5 # [7, 19, 21, 25, 25, (여기), 27, 30, 32, ... ]
💡
search_list
에target
이 몇개 있는지 알고 싶다면?
bisect_right(search_list, target) - bisect_left(search_list, target)
문제 자체가 어려운건 아닌거 같은데 딱봐도 내맘대로 풀면 시간초과일거라고 협박하는 듯한 제한사항의 1,000,000,000명이라는 숫자와.. 아무리 생각해도 이분탐색 알고리즘과 문제가 매치가 안돼서 도대체 어떻게 이게 이분탐색 문제인거지?? 하면서 풀이를 찾아봤다. 한가지 위안인 점 : 구글링할때 이 문제 이분탐색 풀이 감을 못잡았다는 글이 많았다 나만 그런게 아녔어
정말 상상도 못한 아이디어.. ㄴㅇㄱ
구해야하는 것 = 모든 사람이 심사를 받는데 걸리는 "최소" 시간
모든 사람이 심사를 받는데 "시간이 가장 적게" 걸리려면, 같은 시간내에 "최대한 많은 사람"을 심사해야한다.
다시말해, 일정 시간동안 최대한 많은 사람을 심사하려면 모든 심사대에서 쉬지않고 계속 심사를 해야한다. 예를들어 심사대가 3개가 있는데 각각 심사시간이 2분, 3분, 4분(times = [2,3,4]
)이라면, 10분동안 최대한 많이 심사할 수 있는 사람의 수는 2분짜리 심사대에서 5명(10 // 2 = 5
), 3분짜리 심사대에서 3명(10 // 3 = 3
), 4분짜리 심사대에서 2명(10 // 4 = 2
), 해서 총 10명이다.
가능한 모든 시간에 대해서 위 계산을 진행하려면 그 범위는 다음과 같다.
start
= 0end
= 심사시간이 가장 긴 심사대 1개에서 n명을 모두 심사하는 시간 = times[len(times) - 1] * n
그리고 [start, end]
의 범위에 해당하는 시간동안, 이분탐색을 사용해 n명을 모두 심사할 수 있는 최소시간을 찾으면 답이다.
mid
시간동안 최대로 심사할 수 있는 사람의 수(cnt
)를 구하고,
cnt
< n
이라면, mid
시간동안 n
명을 모두 처리할 수 없다는 뜻이므로 탐색범위를 큰쪽(오른쪽)으로 옮긴다. => start = mid + 1
cnt
>= n
이라면, mid
시간동안 n
명보다 많은 사람을 처리할 수 있다는 뜻이므로, 탐색범위를 작은쪽(왼쪽)으로 옮긴다. => end = mid - 1
cnt > n
이 아니라 cnt >= n
이라는 점이다. 원래대로라면 cnt == n
일 때를 따로 빼서 정답을 반환하겠지만, 문제 특성상 이 값이 정확히 맞아떨어지지 않을 수 있고, 여분의 시간을 남긴채로 종료하는게 최선의 선택일 수 있다. 그렇기 때문에 범위를 좁힘과 동시에 혹시 모르니 정답을 옮겨두고 (=>answer = mid
) 끝까지 탐색하는 것이다.풀이 떠올리기가 쉽지 않은데, 정작 구현은 되게 깔끔한 문제였다.
얼마만에 스스로 수월하게 푼 문제인지 엉엉엉엉
입국심사 문제 풀면서 생긴 감으로 이 문제도 처음부터 이분탐색에 맞춰서 생각했다.
구해야하는것 = "바위 사이 간격의 최소값" 중 최대값
-> 탐색범위 = "바위 사이 간격의 최소값"이 될 수 있는 수들 = 바위를 1개, 2개, ... 모두 제거했을때 나올 수 있는 바위 사이 간격의 최소값들 (cf. 바위를 적게 제거할수록 간격이 작고, 많이 제거할수록 간격이 넓어진다.)
주어진 것 = 바위의 위치, 제거해야하는 바위의 수
-> 탐색타겟 = 제거해야하는 바위의 수
그렇다면 탐색범위인 "바위 사이 간격의 최소값"으로부터 "제거해야하는 바위의 수"를 구해야 탐색타겟과 비교를 할 수가 있겠지?
"바위 사이 간격의 최소값"이 N
이어야 할때, 제거해야하는 바위의 수를 구하는 방법
: 앞에서부터 바로 뒤에 있는 바위와의 간격을 보고, 이 간격이 N
보다 작으면 뒤에 있는 바위를 제거하고 제거한 바위와 그 뒤에 있는 바위 사이의 간격에 현재간격을 포함시키도록 값을 업데이트한다. 이 과정을 몇번 반복하는지가 제거해야하는 바위의 수이다.
좀 복잡한데 그림으로 나타내면 다음과 같다.
바위 간격의 최소값이 4여야하기 때문에, 간격이 4보다 작은 경우에는 바위를 제거해서 간격이 4보다 커지도록 늘려야한다.
0 ~ 2
: 간격=2가 4보다 작으므로, 2번 바위 제거 후 다음에 살펴볼 2 ~ 11
간격에 0 ~ 2
간격을 더한다.2 ~ 11
: 간격=9이지만 1번과정에서 2번 바위가 제거되어 0 ~ 2
까지 포함해 사실상 0 ~ 11
이다. 따라서 간격=11, 이는 4보다 크므로 패스한다.11 ~ 14
: 간격=3이 4보다 작으므로, 14번 바위 제거 후 다음에 살펴볼 14 ~ 17
간격에 11 ~ 14
간격을 더한다.14 ~ 17
: 간격=3으로 4보다 작지만 3번과정에서 14번 바위가 제거되어 11 ~ 14
까지 포함해 사실상 11 ~ 17
이다. 따라서 간격=6, 이는 4보다 크므로 패스한다.17 ~ 21
: 간격=4는 4와 동일하므로 패스한다.21 ~ 25
: 간격=4는 4와 동일하므로 패스한다.그럼 2개의 바위를 제거한 후 남은 바위끼리의 간격은 [11, 6, 4, 4]
가 되고, 최소값은 4로, N=4
를 만족한다.
이제 다시 이분탐색으로 돌아와서,
[0, distance]
에서 mid
를 골라, 바위 사이의 간격의 최소값이 mid
가 되기위해 제거해야하는 바위의 수(cnt
)를 계산한다.cnt > n
이라면, 문제에서 주어진 제거해야할 바위의 수보다 많이 제거해야 최소간격이 mid
가 된다는 뜻이므로, 탐색범위를 제거할 바위가 적은 쪽(왼쪽)으로 좁힌다. => end = mid - 1
cnt <= n
이라면, 문제에서 주어진 제거해야할 바위의 수보다 적게 제거해서 최소간격이 mid
가 됐다는 뜻이므로, 탐색범위를 제거할 바위가 많은 쪽(오른쪽)으로 좁힌다. => start = mid + 1
cnt
와 n
이 딱 맞아떨어지지 않을 수 있기 때문에, (바위를 최소 cnt
개만 제거해도 최소간격이 mid
가 되는데, 문제에서 n
개를 제거해야한다고 나와있다면, 그냥 아무 바위나 마저 더 제거하면 된다.) answer
를 이때 저장해두고 다음탐색을 진행했다.하면 끝!
[2,4,10]
이 있을때, 이중 최대값은 10
이지만, 이러저러한 문제조건을 만족하는 최대값은 4
이므로 답은 4
인 것