이진탐색 컨닝페이퍼

이진탐색 일단 기본개념으로 lower bound,upper bound

arr = [1, 2, 3, 3, 5, 6, 6, 8, 9, 10]

left, right = 0, 9

target = 8
answer = -1

while left <= right:
    mid = (left + right) // 2
    if arr[mid] >= target: #요기 >=를 >로 바꾸면 upper bound
        answer = mid
        right = mid - 1
    else:
        left = mid + 1

print(answer) # 7

lower bound 코드다

->  >= 를  >로 바꾸면 upper bound

 

 

이분탐색 쓸거같은 냄새나는거

일단 이분탐색 그냥 뭐 큰숫자 찾는 이런 개념이아니라 그냥 탐색할때 대체적으로 많이 적용할수있는거같음

-> 이런거는 근데 아직까지 쉽게 적용을 못해봄

 

근데 이분탐색 자체가 시간복잡도가  O(logN) 이라서 큰수에 적합함 그래서 문제들 보니까 대체적으로N이 겁나크더라

그래서 뭔가 숫자가 크면 일단 이분탐색도 한번 고려해보고

 

파라메트릭 서치 문제에서 이분탐색으로 해결할수있음 

Parametric Search: 최적화 문제란 문제의 조건에 맞는 특정 변수의 최솟값 혹은 최댓값을 구하는 문제

나무자르기 처럼 뭔가가 주르륵 나열되어있는데 조건에 맞는 최대값 최소값을 구한다면 이진탐색 생각해보자

 

그리고 근데 이분탐색을 하는게  O(logN) 이지 중간에 뭐 계산하고 그러면 그 계산하는걸 따져서 곱해줘야한다 예시로

만약 조건을 확인하는 과정이 O(N) 이라면 전체 시간복잡도는 O(NlogN) 이다.

 

그리고 이분탐색을 쓸거는 뭔가 조건이 연속적으로 참인지 거짓인지가 나와서 그경계선을 찾는거다

 

예를들어

이런식으로 조건이 연속적이여야한다 이렇다면 감이올것이다 이분탐색해야하네

 

 

 

 

문제푸는 대략적인 틀

2512 예산문제인데 대략적인 기본틀이 나온다

import sys

n =int(sys.stdin.readline().rstrip())

budget = list(map(int,sys.stdin.readline().rstrip().split()))

total = int(sys.stdin.readline().rstrip())

#-----------------------------------------------------------------
#여기는 문제의 특정조건 -> 이 문제 만의 것임
S = sum(budget)
if total >= S:
    print(max(budget))
    exit()
#-----------------------------------------------------------------

budget.sort() #sort는 선택사항인데 문제별로 보고 판단해서 하자

#-----------------------------------------------------------------

#여기서 부터 시작 right는 범위 개크게 잡아도 되고 어짜피 logN이라 그닥 상관없음
#아님 그냥 적절히 맞춰서 잡아도됨
left,right = 0, 10**10

#이거 중간값 답 이름은 개떡같이 temp로 했지만 어쩃든 mid값 저장함 여기에 -1로 
#잡은이유는 만약 통과조건이 안되면 -1로 튀어나오도록
temp = -1

#while문 알잘딱하게 하면됨
while left <= right:
    mid =(left + right)//2
    #여기에 대부분 문제에 필요한 경우의수 별로 초기화할 변수들 초기화함 한사이클당 조건
    tempTotal = 0
	
    #맞는지 판단하는것
    for i in budget:
        tempTotal += min(mid,i)
	
    #left right 옮기는 조건
    if tempTotal <= total:
        temp = mid 
        left = mid + 1
    else:
        right = mid - 1


print(temp)

 

이분 탐색 어렵다 잘풀어보자