이분탐색/매개변수 탐색

지니🧸·2023년 3월 28일

알고리즘 코딩테스트 파이썬

알고리즘

목록 보기

1/43

Intro

알고리즘 평가 요소:

실행 시간
메모리 사용
문제 풀이 시간 (시간복잡도)
정확도
예외 처리 능력

이분탐색

선형탐색 vs. 이분탐색

선형 탐색

모든 원소를 순차적으로 탐색
최악의 경우: O(N)회의 탐색

이분 탐색

구간의 길이를 좁혀가며 탐색
i번째 구간의 길이가 N일 때 i+1번째 구간의 길이가 (N+1)/2이하임이 보장
어떠한 경우에도 O(logN)회 안에 탐색 가능
단, 반드시 정렬된 배열에서만 가능
- 정렬하는데 시간이 더 오래 걸리는 상당히 짧은 배열은 이분탐색이 필요 없을수도

배열에 같은 원소가 있다면?

from bisect import bisect_left

index = bisect_left(a, 32)

bisect_left
- 정렬된 배열에서 찾고자 하는 원소보다 크거나 같은 원소 중 가장 작은 것의 인덱스 반환
- bisect_left(배열, 원소)
bisect_right
- 정렬된 배열에서 찾고자 하는 원소보다 큰 원소 중에 가장 작은 것의 인덱스 반환
- bisect-right(배열, 원소)

bisect_left

target > a[mid] : 오른쪽 구간 탐색 (mid 제외)
target == a[mid] : 왼쪽 구간 탐색 (mid 포함)
target < a[mid] : 왼쪽 구간 탐색 (mid 포함)

start = 0
end = arr_size
target = 32
while start < end:
	mid = (start + end) // 2
    if a[mid] < target:
    	start = mid + 1
    else:
    	end = mid
index = start

bisect_right

target > a[mid] : 오른쪽 구간 탐색 (mid 제외)
target == a[mid] : 오른쪽 구간 탐색 (mid 제외)
target < a[mid]: 왼쪽 구간 탐색 (mid 포함)

start = 0
end = arr_size
target = 32
while start < end:
	mid = (start + end) // 2
    if a[mid] <= target:
    	start = mid + 1
    else:
    	end = mid
index = start

BOJ #1920

문제: N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력: 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력: M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

풀이

import sys
from bisect import bisect_left

n = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
B = list(map(int, sys.stdin.readline().split()))

A = sorted(A)

for i in range(m):
    index = bisect_left(A, B[i])
    if index >= len(A):
        print(0)
    elif A[index]==B[i]:
        print(1)
    else:
        print(0)

BOJ #10816

from bisect import bisect_left, bisect_right

n = int(input())
A = list(map(int, input().split()))
m = int(input())
B = list(map(int, input().split()))

A = sorted(A)

for i in range(m):
    left = bisect_left(A, B[i])
    right = bisect_right(A, B[i])
    print(right - left, end=" ")

BOJ #18870

X과 Y좌표를 각각 X좌표, Y좌표 배열에 저장한다 > 메모리 줄이기

import sys
from bisect import bisect_left

n = int(input())
X = list(map(int, sys.stdin.readline().rstrip().split()))

arr = sorted(list(set(X)))
result = [0]*n

for i in range(n):
    result[i] = bisect_left(arr, X[i])
print(*result)

중복제거

for loop 사용

X_unique = [X_sorted[0]]

for i in range(1, n):
	if X_sorted[i] != X_unique[-1]:
    	X_unique.append(X_sorted[i])

dict의 key로 뽑기

X_unique = list(dict.fromkeys(X_sorted))

functools.reduce()

from functools import reduce

X_unique = reduce(lambda acc, cur: acc if cur in acc else acc+[cur], array, [])

매개변수 탐색

단조함수: either 증가 or 감소 둘 중 하나만

f(x) = K를 만족하는 x를 구하시오
- 역함수) x = f-1(K)
역함수를 계산하기 어려운 경우는?
- x를 추정하여 f(x)를 계산
- f(x)와 K를 비교 > 이분 탐색
- 단, 함숫값을 미리 계산할 필요는 없음
- 시간 복잡도: ((f(x)를 구하는 시간 복잡도) * log(초기 구간의 크기))

예시) f(x) = 2x^2 + x일때 f(x)>=50을 만족하는 자연수 x의 최솟값은?

f(x)는 단조함수가 아니긴 하지만 x>0일 때는 단조함수임
x 배열 중 중간값의 f(x)를 구한 다음 50과 비교
- f(x)가 50보다 크면 x를 왼쪽 구간의 중앙값
- f(x)가 50보다 작으면 x를 오른쪽 구간의 중앙값
시작점과 끝점이 같아지면 정답

BOJ #1654

f(mid) >= n : 오른쪽 구간 탐색 (mid 포함)
f(mid) < n : 왼쪽 구간 탐색 (mid 제외)

k, n = map(int, input().split())
a = []
for i in range(k):
	a.append(int(input()))
    
start = 1
end = 2 ** 31

while start < end:
	mid = (start + end + 1) // 2
    f = 0
    for i in range(k):
    	f += a[i] // mid
    if n <= f:
    	start = mid
    else:
    	end = mid - 1
print(start)

함수값이 n이상이면서 가장 오른쪽에 있는 값을 찾는 코드

f(mid) >= n : 오른쪽 구간 탐색 (mid 제외)
f(mid) < n : 왼쪽 구간 탐색 (mid 포함)

k, n = map(int, input().split())
a = []
for i in range(k):
	a.append(int(input()))
    
start = 1
end = 2 ** 31

while start < end:
	mid = (start + end) // 2
    f = 0
    for i in range(k):
    	f += a[i] // mid
    if n <= f:
    	start = mid + 1
    else:
    	end = mid
print(start)

함수값이 n미만이지만 가장 작은 x값
결과값에서 1을 빼면 첫 코드와 같은 값

무한루프 가능성

start = 1, end = 2인 경우 고려
고려할 점
- 최댓값, 최솟값을 초기 bound 값으로 설정하였는가?
- 구간을 정확히 절반으로 나누었는가?
  - 총길이가 짝수면 구간의 길이가 같아야함
- 문제의 상황에 맞는 이분탐색을 구현하였는가?

BOJ #2343

블루레이의 크기를 직접 찾지 말고 블루레이의 크기를 가정하고 필요한 블루레이의 개수를 찾자

br_size = 크기
br_time = 시간이 얼마나 찼는지
br_num = 완성된 블루레이 개수

for i in range(n):
	if a[i] > br_size:
    	br_num = i << 30
        break
	if br_time + a[i] > br_size:
    	br_time = a[i]
        br_num += 1
    else:
    	br_time += a[i]
br_num += 1

n, m = map(int, input().split())
a = list(map(int, input().split()))
start = 1
end = 1 << 30
while start < end:
	br_size = (start + end) // 2
    br_num = 0
    br_time = 0