이진 탐색 문제풀이

1. 수 찾기 (백준 1920 번)

1920번: 수 찾기

 

직접 작성한 코드) 

 

n=int(input())
array=list(map(int, input().split()))
m=int(input())
targetlist=list(map(int,input().split()))


array.sort()
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)

for i in targetlist:
    result=binary_search(array,i,0,n-1)
    if result==None:
        print(0)
    else:
        print(1)

 

2. 숫자 카드 (백준 10815 번)

10815번: 숫자 카드

 

직접 작성한 코드) 

n=int(input())
array=list(map(int, input().split()))
m=int(input())
targetlist=list(map(int,input().split()))
lastresult=[]

array.sort()
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)

for i in targetlist:
    result=binary_search(array,i,0,n-1)
    if result==None:
        lastresult.append(0)
    else:
        lastresult.append(1)

for i in lastresult:
    print(i,end=' ')

 

3. 가장 긴 증가하는 부분 수열 2 (백준 12015 번)

12015번: 가장 긴 증가하는 부분 수열 2

 

참고 코드)

 

n=int(input())
array=list(map(int,input().split()))
import sys
from bisect import bisect_left

lis = []
result = 0
for num in array:
    if not lis:
        lis.append(num)
        result += 1
        continue
    
    if lis[-1] < num:
        lis.append(num)
        result += 1
    else:
        index = bisect_left(lis, num)
        lis[index] = num
    
  
print(result)

 

➡️ 핵심 아이디어

만약, 현재 lis이 10, 30, 40, 70으로 구성되어 있고, 현재 50이 들어갈 자리가 70이 있는 자리인 상황이라면 70을 50으로 교체해야 더 긴 수열을 연장할 수 있다.

왜냐하면, 10, 30, 40, 70 일때 60가 들어온다면 추가할 수 없지만 10, 30, 40, 50 일 경우에는 추가하여 result를 더 크게 만들 수 있다.

이를 위한 코드가 else: 이후의 코드이다.

 

4. 예산 (백준 2512번)

2512번: 예산

 

참고 코드) 

 

n=int(input())
array=list(map(int,input().split()))
number=int(input())

start,end=0,max(array)
total_budget=0

if sum(array)>=end:
    print(max(array))
    
else:
    while start<=end:
        mid=(start+end)//2
        total_budget=0
        for i in array:
            total_budget+=min(mid,i)
        if total_budget>number:
            end=mid-1
        else:
            start=mid+1
            
    print(mid)

 

➡️ 핵심 아이디어: 적절한 값을 찾아야하는 문제이다. 이진 탐색을 통하여 가장 큰 값을 바꾸며 합을 구하면서 적절 값을 찾는다.