이진 탐색
개요
레크레이션 게임 중에 진행자가 1부터 100까지의 수 중에 생각한 숫자를 맞추는 게임이 있다. 일명 업앤다운 게임이라고 한다. 가장 적은 트라이로 확실하게 정답을 맞출 수 있는 방법이 무엇일까?
예를 들어 진행자가 생각한 숫자가 70이라고 해보자.
그럼 한 번에 문제를 해결할 확률은 1퍼센트다. 누가 말했던 숫자를 까먹을 수도 있으니 1부터 100까지 부르기 시작하면 확실히 맞출 수 있다. 그러나 좀 더 스마트하게 풀 수 있는 방법은 없을까?
한 명이 50을 부르고 답은 70이니 진행자는 up을 말한다. 이렇게 찍기 전에 범위를 제한시키고 찍으면 확률은 1/100이었던 것이 1/50까지 높아진다.
계속 이렇게 범위를 제한시켜가면 단순 찍기로 맞추는 것보다 맞출 확률이 올라간다.
위와 같은 방법으로 맞추기 시작한다면 7번만에 맞출 수 있다.
이와 같은 전략을 이진 탐색(Binary search)라고 부른다.
1부터 순차적으로 탐색한다면 최악의 경우 100번의 연산을 해야하지만 위와 같은 방식으로 탐색한다면 최악의 경우에도 7번만의 연산으로 찾을 수 있다.
주의할 점은 위에서 살펴본 게임처럼 데이터가 정렬되어 있어야한다는 것이다.
기본 코드
def binary_search(array, target, start, end):
while start <= end:
mid = (start + end) // 2
if array[mid] == target:
return mid
elif array[mid] > target:
end = mid - 1
else:
start = mid + 1
return None
n, target = list(map(int, input().split()))
array = list(map(int, input().split()))
result = binary_search(array, target, 0, n - 1)
if resut == None:
print("원소가 존재하지 않음.")
else:
print(result + 1)
- 반복문을 돌며 시작 값과 끝 값의 중간 값을 구한다.
- 만약 배열의 중간 값과 타겟이 일치하면 중간 인덱스를 리턴한다. 즉, 원하는 값을 찾은 것이다.
- 만약 이렇게 찾은 값이 타겟보다 더 크다면 끝 점을 mid - 1로 갱신한다.
- 그게 아니라면 즉 더 작다면 시작점을 mid + 1로 갱신한다.
위의 코드는 반복문을 사용한 코드로 아래와 같이 재귀 함수로도 구현할 수 있다.
def binary_search(array, target, start, end):
if start > end:
return None
mid = (start + end) // 2
if array[mid] == target:
return mid
elif array[mid] > target:
return binary_search(array, target, start, mid - 1)
else:
return binary_search(array, target, mid+1, end)
이진 탐색의 시간 복잡도는 다음과 같이 계산된다.
n / 2
n / 2 / 2
n / 2 / 2 / 2
...
n * (1/2) ^ k = 1(k번 반복 끝에 결국 탐색범위가 1이 되므로)
2 ^ k = n
k = log2(n)
따라서 이진 탐색의 시간 복잡도는 O(logn)이 된다.(극한에서 상수는 무시한다.)
문제의 데이터가 너무 크다면 이진탐색일 가능성이 높다. 많은 데이터 중에 한 건을 빠르게 찾을 수 있기 때문이다.
탐색 범위가 2,000만이 넘어가면 이진 탐색 문제일 가능성이 있다고 한다.
알아두면 좋은 라이브러리로는 bisect가 있다.
예를 들어 정렬된 정수배열이 있다고 했을 때 특정 요소를 배열에 추가하되 추가한 다음에도 정렬된 상태를 유지하고 싶을 수 있다.
그럴 땐 이렇게 코드를 작성할 수 있다.
for index in range(len(배열))
if 새로운 요소 <= 배열[index]:
return index
위의 코드는 O(N)의 시간복잡도를 가지게 된다. 데이터가 커지게되면 비효율적이다. 이럴 때 이진탐색을 적용해볼 수 있다.
left, right
while left <= right:
mid = (left + right) // 2
if 배열[mid] >= n:
result = mid
else:
left = mid + 1
return result
위와 같은 코드를 구현하고 있는 것이 bisect라이브러리다.
from bisect import bisect_left, bisect_right
bisect_left(배열, 타겟)
bisect_right(배열, 타겟)
이를 응용해서 특정 범위에 속하는 원소의 갯수도 구할 수 있다.
def count_by_range(배열, left_value, right_value):
right_index = bisect_right(a, right_value)
left_index = bisect_left(a, left_value)
return right_index - left_index
문제풀이
공유기 설치
백준 2110
문제
도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.
도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.
C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.
입력
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.
출력
첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.
예제 입력 1
5 3
1
2
8
4
9
예제 출력 1
3
5개의 집의 좌표가 주어졌고 3개의 공유기를 설치해야한다.
일단 예제 입력을 받고 정렬해야할 필요가 있다.
정렬하면 1, 2, 4, 8, 9가 되고 1번, 4번 8번에 공유기를 설치하면 가장 인접한 두 공유기의 거리는 4 - 1로 3이 된다.
좌표의 최대 범위가 굉장히 크므로 이진 탐색을 적용해볼 수 있겠다.
최소 거리는 1로 일단 모든 집에 공유기를 설치하는 것이다. 이렇게 하면 공유기의 개수가 조건보다 많아질 것이다.
최대 거리는 8로 양 끝단에 공유기를 설치하는 것이다. 이렇게 하면 일반적으론 공유기의 개수가 조건보다 적을 것이다.
거리의 범위인 1~8까지에서 거리를 적절히 조절하여 문제에서 주어진 공유기의 개수를 설치할 수 있는지 보면 된다.
n, c = list(map(int, input().split()))
array = []
for _ in range(n):
array.append(int(input()))
array.sort()
start = 1
end = array[-1] - array[0]
result = 0
while start <= end:
mid = (start + end) // 2
value = array[0]
count = 1
for i in range(1, n):
if array[i] >= value + mid:
value = array[i]
count += 1
if count >= c:
start = mid + 1
result = mid
else:
end = mid - 1
print(result)
입국 심사
n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.
처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.
모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.
입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.
예시
n = 6, times = [7, 10], return 28
최솟값을 찾아야하고 일정 값에 대해 1번 창구에서 처리할 수 있는 사람의 수를 더해서 시간이남는지 시간이 부족한지 판단하면 된다.
이진 탐색 문제다.
정각에 시작한다고 가정
0분 1번 창구로 1명, 2번 창구로 1명
7분이 되면 1번 창구에 1명이 더 들어감.
10분이 되면 2번 창구에 1명 들어감.
14분이 되면 1번 창구에 1명 들어감.
20분 1분 기다려서 심사를 받으면 21 + 7 //28분
이렇게 해서 모든 사람이 심사를 받을 수 있는 가장 최소(최적)시간은 28분이다.
문제를 분석해 보면 심사원 한 명이 심사하는데 걸리는 시간은 최소 1분이므로 가장 비효율적으로 심사가 이루어진 경우는 가장 시간이 많이 걸리는 창구에서만 일을 처리했을 경우로
max(times) * n이 되고 가장 최소의 시간은 이진 탐색을 적용하기 위해서 1분으로 설정한다.
예시를 생각해봤을 때 최소 시간은 1분이고 최대 시간은 10 * 6으로 60분이다.
첫번째 이진 탐색
중앙 값인 30분으로 이진 탐색을 시작해보자.
30분 동안 처리할 수 있는 사람의 수는 각각 30 // 7 그리고 30 // 10이 된다.
총 처리할 수 있는 사람의 수는 4 + 3 = 7이 된다.
6명만 심사하면 되기 때문에 왼쪽 범위를 탐색한다.
중앙 값에서 1을 줄인 값을 상한치로 설정한다.
두번째 이진 탐색
왼쪽 중앙 값을 가지고 다시 이진 탐색을 한다.
mid = (1 + 29) // 2 = 15
1번 심사관 15 // 7 = 2
2번 심사관 15 // 10 = 1
총 처리할 수 있는 사람 수는 3명이다.
시간이 부족했다는 의미이다. 따라서 15를 기준으로 왼쪽 범위를 탐색한다.
left = 15 + 1 = 16
세번째 이진 탐색
left = 16, right = 29
새로 중앙 값을 갱신한다.
중앙 값은 (16 + 29) // 2 = 22
1번 심사관은 22 // 7 = 3
10분 심사관은 22 // 10 = 2
총 처리할 수 있는 사람 수는 5명이다.
아직 시간이 부족하다.
left를 증가시킨다.
left = 22 + 1
네번째 이진 탐색
left = 23, right = 29
mid = (23 + 29) // 2 = 26
1번 심사관은 26 // 7 = 3명
2번 심사관은 26 // 10 = 2명
아직도 시간이 부족하니 left값을 증가시킨다.
left = 26 + 1 = 27
다섯번째 이진 탐색
left = 27, right = 29
mid = (27 + 29) // 2 = 28
1번 심사관은 28 // 7 = 4
2번 심사관은 28 // 10 = 2
mid시간이 충분하다. right를 1줄인다.
right = 29 - 1 = 28
여섯번째 이진 탐색
mid = (27 + 28) / 2 = 27
심사할 수 있는 총 사람은 5명으로 6명을 심사하기엔 시간이 부족하다. 따라서 left값을 증가시킨다.
이렇게 하면 left = 28, right = 28로 최소 시간을 찾았으니 탐색을 종료한다.
풀이 코드는 아래와 같다.
def solution(n, times):
min_time, max_time = 1, max(times) * n
while min_time <= max_time:
mid = (min_time + max_time) // 2
total = sum(mid // time for time in times)
if total >= n:
max_time = mid - 1
else:
min_time = mid + 1
return min_time
동작과는 관계없이 이진 탐색의 의미를 살려 left, right로 설정하는 것도 좋은 생각이다.
가사 탐색
문제설명
친구들로부터 천재 프로그래머로 불리는 "프로도"는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.
그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "fro??"는 "frodo", "front", "frost" 등에 매치되지만 "frame", "frozen"에는 매치되지 않습니다.
가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 queries가 주어질 때, 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 반환하도록 solution 함수를 완성해 주세요.
가사 제한사항
words의 길이(가사 단어의 개수)는 2 이상 100,000 이하입니다.
각 가사 단어의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
전체 가사 단어 길이의 합은 2 이상 1,000,000 이하입니다.
가사에 동일 단어가 여러 번 나올 경우 중복을 제거하고 words에는 하나로만 제공됩니다.
각 가사 단어는 오직 알파벳 소문자로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.
검색 키워드 제한사항
queries의 길이(검색 키워드 개수)는 2 이상 100,000 이하입니다.
각 검색 키워드의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
전체 검색 키워드 길이의 합은 2 이상 1,000,000 이하입니다.
검색 키워드는 중복될 수도 있습니다.
각 검색 키워드는 오직 알파벳 소문자와 와일드카드 문자인 '?' 로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.
검색 키워드는 와일드카드 문자인 '?'가 하나 이상 포함돼 있으며, '?'는 각 검색 키워드의 접두사 아니면 접미사 중 하나로만 주어집니다.
예를 들어 "??odo", "fro??", "?????"는 가능한 키워드입니다.
반면에 "frodo"('?'가 없음), "fr?do"('?'가 중간에 있음), "?ro??"('?'가 양쪽에 있음)는 불가능한 키워드입니다.
이렇게 보면 어려우니 먼저 예시를 통해 이해해보는 편이다.
words queries result
["frodo", "front", "frost", "frozen", "frame", "kakao"] ["fro??", "????o", "fr???", "fro???", "pro?"] [3, 2, 4, 1, 0]
fro??의 경우 `frodo`, `front`, `froest`와 메치되니 3,
????o의 경우 `frodo`, `kakao`와 매치되니 2,
fr???은 `frodo`, `front`, `frost`, `frame`에 매치되니 4...
만약 fro??의 경우 모든 요소를 검색해볼 필요없이 5글자의 가사중에서 fro로 시작하는 요소를 찾으면 된다.
fro로 시작하는 마지막 단어의 위치를 찾고 fro로 시작되는 첫 단어의 위치를 찾아서 마지막 인덱스 - 처음 인덱스를 구하면 된다.
from bisect import bisect_left, bisect_right
def count_by_range(a, left_value, right_value):
right_index = bisect_right(a, right_value)
left_index = bisect_left(a, left_value)
return right_index - left_index
array = [[] for _ in range(10001)]
reversed_array = [[] for _ in range(10001)]
def solution(words, queries):
answer = []
for word in words:
array[len(word)].append(word)
reversed_array[len(word)].append(word[::-1])
for i in range(10001):
array[i].sort()
reversed_array[i].sort()
for q in queries:
if q[0] != '?':
res = count_by_range(array[len(q)], q.replace('?', 'a'), q.replace('?', 'z'))
else:
res = count_by_range(reversed_array[len(q)], q[::-1].replace('?', 'a'), q[::-1].replace('?', 'z'))
answer.append(res)
return answer
정렬된 배열에서 특정 수의 개수 구하기
Zoho 인터뷰
N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어있다.
이 때 이 수열에서 x가 등장하는 횟수를 계산하세요. 예를 들어 수열 [1,1,2,2,2,2,3]이 주어졌고 x가 2라면 현재 수열에서 2가 4번 등장하므로 4를 출력한다.
시간제한: 1초
주어지는 데이터의 개수: 1 <= N <= 1,000,000
각 원소의 값 : 10^-9 <= 원소의 값 <= 10^9
입력
7 2
1 1 2 2 2 3
출력
4
입력
7 4
1 1 2 2 2 3
출력
-1
일반적으로 파이썬 프로그램에선 2천만 번 ~ 1억 번의 연산을 1초에 수행한다고 예측할 수 있으니 순차탐색을 하더라도 1초 안에 수행할 수 있을 것 같지만 문제에서는 이진탐색을 사용하라는 조건이 있다.
직접 카운팅을 하는 방법이 아니라면 이렇게 생각해볼 수 있다. 2의 개수 = 가장 마지막으로 2가 등장한 인덱스 - 가장 처음으로 2가 등장한 인덱스 + 1
이렇게 하면 특정 요소를 찾고 그 왼쪽과 오른쪽에 가장 마지막으로 등장하는 번째의 인덱스를 반환하는 문제가 된다.
n, x = map(int, input().split())
array = list(map(int, input().split()))
start = 0
end = n-1
def count_by_value(start, end, array, target):
mid = (start + end) // 2
fi = first(start, end, array, target)
li = last(start, end, array, target)
if fi == None:
return 0
else:
return fi - li + 1
def first(start, end, array, target):
if start > end:
return None
mid = (start + end) // 2 # 1
if ((array[mid - 1] < target) or mid == 0) and (array[mid] == target):
return mid
elif array[mid] >= target:
return first(start, mid - 1, array, target)
else:
return first(mid + 1, end, array, target)
def last(start, end, array, target):
if start > end:
return None
mid = (start + end) // 2
if ((mid == n - 1) or target < array[mid + 1]) and array[mid] == target:
return mid
elif array[mid] > target:
return last(start, mid - 1, array, target)
else:
return last(mid + 1, end, array, target)
result = count_by_value(start, end, array, x)
if result == 0:
print(-1)
else:
print(result)
bisect를 이용하면 코드가 더 간단해진다.
from bisect import bisect_left, bisect_right
def count_by_range(array, left, right):
ri = bisect_right(array, right)
li = bisect_left(array, left)
return ri - li
n, x = map(int, input().split())
array = list(map(int, input().split()))
count = count_by_range(array, x, x)
if count == 0:
print(-1)
else:
print(count)
풀이 출처 : 이코테 - 동빈나