Algorithm ) Binary Search 문제

파이썬 이진 탐색 라이브러리 

 

bisect_left(a,x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환

bisect_right(a,x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환

from bisect import bisect_left, bisect_right

=> 값이 특정 범위에 속하는 데이터 개수 구하기

from bisect import bisect_left, bisect_right

# 값이 left_value, right_value인 데이터 개수를 반환하는 함수 
def count_by_range(a, left_value, rignt_value):
	right_index = bisect_right(a, right_value)
    left_index = bisect_left(a, left_value)
    return right_index - left_index

파라메트릭 서치

 

최적화 문제를 결정 문제로 바꾸어 해결하는 것

=> 이진탐색으로 해결해보자 !

---

문제 1. 부품 찾기

 

전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다.

어느 날 손님이 M개의 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다.

손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다.

이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자.

 

예를 들어 가게의 부품이 총 5개일 때 부품 번호가 다음과 같다고 하자.

N=5 [8, 3, 7, 9, 2]

손님은 총 3개의 부품이 있는지 확인 요청했는데 부품 번호는 다음과 같다.

M=3 [5, 7, 9]

이때 손님이 요청한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes를,

없으면 no를 출력한다. 구분은 공백으로 한다.

 

소스코드

 

# 이진 탐색 소스코드 구현
def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        # 찾은 경우 중간점 인덱스 반환
        if array[mid] == target:
            return mid
        # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
        elif array[mid] > target:
            end = mid - 1
        # 중간점의 값보다 찾고자 하는 값이 작은 경우 오른쪽 확인
        else:
            start = mid + 1
    return None

# 가게의 부품개수, 가게에 있는 전체 부품 번호 입력
n = int(input())
shop_array = list(map(int, input().split()))
shop_array.sort() # 이진탐색을 수행하기 위해서 정렬하자 !

# 손님이 요청한 부품개수, 요청한 부품 번호
m = int(input())
want_array = list(map(int, input().split()))

# 손님이 요청한 부품 번호를 하나씩 확인 
for i in want_array:
    #해당 부품이 존재하는지 확인 
    result = binary_search(shop_array, i, 0, n-1)
    if result != None:
        print("yes", end= ' ')
    else:
        print('no', end= ' ')

 

문제 2. 떡볶이 떡 만들기 

 

절단기에 높이 H를 지정하면 줄지어진 떡을 한번에 절단합니다. 

높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않습니다.

 

예를 들어 19 14 10 17cm 인 떡이 나란히 있고

절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 

15, 14, 10, 15cm 가 될 것 입니다. 

잘린 떡의 길이는 차례대로 4,0,0,2 cm 입니다. 

손님은 6cm 만큼의 길이를 가져갑니다. 

 

손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 

절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램 작성

 

문제 해결 아이디어 

=> 적절한 높이를 찾을 때까지 이진탐색을 수행하여 높이를 반복해서 조정한다. 

 

현재 이 높이로 자르면 조건을 만족할 수 있는가를 학인한 뒤에

조건의 만족 여부에 따라서 탐색 범위를 좁혀서 해결 ! 

여기서 절단기의 높이는 0부터 10억까지의 정수 중 하나 ?

이렇게 큰 탐색범위를 보면 가장 먼저 이진 탐색을 떠올리자 ! 

 

입력 예시 :

떡의 개수 4 요청한 길이 6 

떡의 길이 19 15 10 17

 

[1단계] 시작점 : 0, 끝점 : 19 , 중간점: 9

중간점으로 자르면, 10, 6, 1, 8 - 결과저장

=> 조건 충족 : 중간점 + 1 을 시작점으로 설정한다. 

 

[2단계] 시작점 : 10 , 끝점 : 19, 중간점 : 14

중간점으로 자르면, 5, 1, 0, 3 - 결과저장

=> 조건 충족 : 중간점 +1 을 시작점으로 설정한다. 

 

[3단계] 시작점 : 15, 끝점 : 19 , 중간점 : 17

중간점으로 자르면, 2,0 ,0 ,0 - 결과 저장 ㄴㄴ

=> 조건 충족 못함 : 끝점을 중간점 -1 로 설정

 

[4단계] 시작점 : 15, 끝점 : 16, 중간점 : 15 

중간점으로 자르면, 4,0,0,2 

=> 조건 충족 ! 더이상 탐색 범위가 줄어들 수 없음 ! 

 

중간점의 값은 시간이 지날수록 최적화된 값이 되기 때문에, 

과정을 반복하면서 얻을 수 있는 떡의 길이 합이 

필요한 떡의 길이보다 크거나 같을 때마다 중간점의 값을 기록하자 !

 

# 떡의 개수와 요청한 떡의 길이를 입력
n, m = map(int, input().split())
array = list(map(int, input().split()))

# 시작점과 끝점 설정
start = 0
end = max(array)

# 이진 탐색 수행 (반복적)
result = 0

while(start <= end):
    total = 0 # 총 잘리는 떡의 길이
    mid = (start+end) // 2

    for x in array:
        if x > mid: # 절단기 길이보다 떡 길이가 길면 절단 가능
            total += x - mid # 떡 길이 - 절단기 길이 // 잘랐을 때 떡의 양 계산
        if total < m:
        # 요청한 떡 길이보다 작으면? 더 잘라야겠지 ? 절단기를 더 앞으로, 종료점을 중간점 -1 로
            end = mid -1
        else: # 필요한 떡의 길이가 요청한 길이보다 클 경우 - 최대한 덜 잘라야함 시작점을 중간점 +1 로
            result = mid # 최대한 덜 잘랐을 떄가 정답이므로, 여기서 기록해주기
            start = mid + 1

print(result)