이분탐색
1. 개요
가. 문서 목적
이분탐색에 대해 정리한 글이다.
나. 목차
2. 시간 복잡도
모든 알고리즘에서 시간복잡도는 빼먹을 수 없다. 왜냐하면 가장 효율적인 알고리즘을 찾아 컴퓨터 연산량을 줄임으로서 회사에게 이득이 될 수 있고 빠른 사용자 응답 제공으로 이탈률을 줄일 수 있기 때문이다.
이분탐색의 시간복잡도는 정렬 후에 빨라진다. 만약 탐색을 한번만하고 대상 배열을 안 쓸 예정이라면 정렬을 할 필요가 없다. 왜냐하면 정렬에는 O(nlogn)이 사용된다. 만약 당신이 병합 정렬을 쓴다면 말이다. 순차탐색은 n 이므로 한번만 할 시에는 O(n)이다. 하지만 만약 여러번의 탐색을 진행한다면 이야기가 달라진다. 순차탐색은 매번 O(n)을 여러번인 n번 만큼 진행하기 때문에 시간복잡도는 O(n^2)을 의미한다. 하지만 이분탐색은 O(logn)을 여러번인 n번 만큼 진행한다면 O(nlogn)이 되므로 순차탐색보다 빠르다. 여기서 집중해야할 점은 한번 탐색하는게 아닌 여러번 탐색하는 경우에 이미 정렬된 배열을 1/2씩 쪼개면서 탐색하는 이분탐색은 O(logN)의 성능을 가졌기 때문으로, 매번 O(n)이 시행되어야 하는 순차탐색보다 빠르다는 것이다.
결국 이분탐색은 초기 O(nlogn)인 정렬만 해주면 되는 처음에만 힘이 빡 들어가는 그 뒤에는 순탄한 알고리즘 인 것이다.
하지만 새로운 데이터가 계속 추가된다면? 그때는 이분탐색을 사용해서 들어갈 위치를 찾고 그 위치의 뒤에 원소들을 한칸씩 뒤로 밀면 되므로, O(logn) + O(n) = O(n)이 된다.
3. mid
(left+right) // 2 = mid
4. 진행 방법
mid를 먼저 구하고 찾고자 하는 값이 mid면 그 값이나 인덱스를 출력한다. 만약 아니라면 mid와 대소비교를 진행한다. mid보다 크면 left = mid +1, 작다면 right = mid -1이다.
5. 키워드
- left = mid + 1
- right = mid - 1
- left <= right : 결국 마지막에 같은 값이 되서
6. 느낀점
내 생각에 알고리즘은 뚝심이다. 끝까지 풀어서 모든 로직의 이유를 경험하여 직관적으로 풀 수 있게 만드는 "뚝심"
7. 시간초과
import sys
input = sys.stdin.readline
N = int(input())
a = sorted(list(map(int, input().split())))
M = int(input())
n_arr = list(map(int, input().split()))
def bs(n):
left = 0
right = N-1
while left <= right:
mid = (left + right) // 2
if n == a[mid]:
return mid
elif n <= a[mid]:
right = mid -1
else:
left = mid + 1
return -1
def find_left_right(idx, n):
origin_idx = idx
cnt = 1
start_idx = 0
end_idx = N-1
# 왼쪽 찾기
while idx > 0 :
idx -=1
if a[idx] == n:
cnt+=1
else:
break
idx = origin_idx
# 왼쪽 찾기
while idx < end_idx :
idx +=1
if a[idx] == n:
cnt+=1
else:
break
return cnt
# 오른쪽 찾기
ans = []
for n in n_arr:
cnt=0
idx = bs(n)
if idx == -1:
cnt = 0
else:
cnt = find_left_right(idx, n)
ans.append(cnt)
for i in ans:
print(i, end=" ")8. 문제
가. 백준 1920
import sys
input = sys.stdin.readline
N,K = map(int, input().split())
a=[]
for i in range(N):
a.append(int(input()))
# 이분탐색
max_num = max(a)
left = 1
right = max_num
ans = 0
while left <= right:
mid = (left + right) //2
cnt = 0
for i in a:
cnt += i//mid
if cnt >= K :
left = mid + 1
ans = mid
else:
right = mid - 1
print(ans)
# 결론
# 1. 더 긴 선의 길이로 얻고자하는 선의 개수만큼 얻을 수 있다면
# mid보다 큰 값 = left = mid + 1로 탐색을 진행하면 되고
# 2. 얻고자하는 선의 개수를 만족하지 않아, 선을 더 작게 가져가야 한다면
# mid보다 작은 값 = right = mid - 1로 탐색을 진행해야 한다.
