3. 이진탐색

이진탐색? 오름차순으로 정렬된 리스트에서, 특정한 값의 위치를 찾는, 알고리즘

 

찐 의미는 검색범위를 줄여나가며 원하는 데이터를 검색하는 알고리즘임

 

1부터 100까지의 수를 던져... 그 중에 너가 원하는 수가 있어...

걔를 찾기 위해 

완전탐색을 하면 최대 100번 체크하겠죠? -시간복잡도o(n)

 

근데 얘를 50! 아냐 작어... 25!! 아냐 커... 38!!! 까비 좀 더 작음

이렇게 중간값으로 말해보고 큰지작은지 힌트 받는다고 생각해봐 정말 오래걸려도 6번이면 끝날듯

- 시간복잡도 O(logN) 

리스트 정렬이 필요하다면 - O(NlogN)이 되겠지?

이진탐색기본코드

num=49
left=1
righr=100
while left<=right: #l이랑 r이 엇갈리는순간이오면 모든범위본거니까...
    mid=(left+right)//2 #l과 r의 중간값 짝수면 더작은쪽
    if mid == num: 
        break
    elif mid<num: #mid 오른쪽에 num이있는거니까
        left=mid+1 #왼쪽을 mid오른쪽에두기
    elif mid>num: #mid 왼쪽에 num
        right=mid-1 #r을 mid바로왼쪽에

 

 

*말도안되는 입력값의범위가 주워진다면 바로 이진탐색을 생각해보세요!

~그럼 문제 몇 개 풀어보시길-...~

13423번: Three Dots (acmicpc.net)

13423번: Three Dots

t=int(input())
for _ in range(t):
    n=int(input())
    nrr=sorted(list(map(int,input().split())))
    m=0 #경우의 수 세기
    for i in range(n-1):
        for j in range(i+1,n):
            l=i
            r=j
            a = (nrr[r] + nrr[l]) / 2
            if a in nrr:
                m += 1
    print(m)

충격실화.

in함수는 시간복잡도 O(N)임... 전부 다 보는 거라...

어이없어. 이래서 이진탐색써야되는구나~~

t=int(input())
for _ in range(t):
    n=int(input())
    nrr=sorted(list(map(int,input().split())))
    m=0 #경우의 수 세기
    for i in range(n-1):
        for j in range(i+2,n):
            l=i
            r=j
            a = (nrr[r] + nrr[l]) / 2
            while l<=r:
                mid=(l+r)//2
                if a==nrr[mid]:
                    m+=1
                    break
                elif a>nrr[mid]:
                    l=mid+1
                elif a<nrr[mid]:
                    r=mid-1
    print(m)

in 함수 대신 이진탐색 사용.

이중 for문으로 모든 두개를 잡고 그애들의 중간값이 존재하면 m+=1.

근데 둘이 딱 붙어있으면 중간값이 어딨음? 그래서 두 번째 for 문은 i+2부터 시작으로 바꿨음.

 

16401번: 과자 나눠주기 (acmicpc.net)

16401번: 과자 나눠주기

m,n=map(int,input().split())
l=sorted(list(map(int,input().split())))
if m> sum(l):
    x=0
else:
    left=1
    right=l[-1]
    while left<=right:
        mid=(left+right)//2
        cnt=0
        for i in range(n):
            cnt+=l[i]//mid
        if cnt>=m:
            x=mid
            left=mid+1
        else:
            right=mid-1

print(x)

가장 작은 자연수인 1의 길이도 안되면 0으로 출력

그게 아니라면 줄 수 있는 가장 긴 길이를 찾기 위해 이진탐색.

가장 작은 길이인 1, 가장 큰 길이를 left와 right로 두고

mid를 가장 긴 길이라고 설정하여 검증.

모든 l을 mid의 길이로 나눴을때 그 수가 아이들의 수m보다 크면 정답일 수 있으니 x에 저장.

이보다 큰 수를 검증해보기위해 left를 mid보다 1큰수로 저장하고 다시 탐색

만약 mid로 나눴을때 m보다 작으면 길이를 더 줄여야하므로 right를 mid-1로 주고 다시 탐색

 

17951번: 흩날리는 시험지 속에서 내 평점이 느껴진거야 (acmicpc.net)

17951번: 흩날리는 시험지 속에서 내 평점이 느껴진거야

최대한 k개의 그룹의 각각의 점수합을 비슷하게 맞춰야겠다.

순서는 바꿀 수 없고

만약 k가 n이면 단순히 가장 작은 x를 출력

만약 k가 1이면 단순히 x의 모든 합을 출력

그게 아니라면, '가장작은x'와 '모든x의합'의 중간값을 출력해야함. 여기서 이진탐색.

그 값으로 묶이는 그룹이 존재해야함. 다른 그룹들은 그 값보다 큰 값으로 묶여야함.

n, k=map(int,input().split())
x=list(map(int,input().split()))
if k==1:
    ans=sum(x)
elif k==n:
    ans=min(x)
else:
    l=min(x)
    r=sum(x)
    while l<=r:
        mid=(l+r)//2
        ss=0
        p=0
        for i in range(n):
            ss+=x[i]
            if ss>= mid:
                p+=1
                ss=0
        if p>=k:
            ans=mid
            l=mid+1
        else:
            r=mid-1
print(ans)

 

 

근데

사실

위 문제랑 너무너무 비슷했음... 위 문제 풀이를 아니까

얘도 그럭저럭...

이진탐색을 사용하는 방식이 완전히 똑같았고

mid검증하는건 그냥 그게 진짜 답이라면~~ 앞에서부터 끊어나가면 딱 맞겠지~~ 하면서

for문 만들고. 만약 k보다 많이 잘리면 답 후보로 넣고 또 돌려~~

이부분도 위에 문제랑 같았음.