<PART 2> 이진탐색-예제

<2>부품찾기
전자 매장에는 부품이 N개 있습니다. 그리고 부품마다 고유 부품 번호가 존재합니다.
여기서 손님이 M개의 부품과 고유 부품 번호를 물어봐서 각각이 있는지 확인해야 합니다.
있으면 yes, 없으면 no를 출력하는 프로그램을 작성해봅니다.
(1<= N <= 1,000,000), (1<=M<=100,000)

입력예시)
5
8 3 7 9 2
3
5 7 9

출력 예시)
no yes yes

def binary_search(array,target,start,end):
    # 찾는 원소가 없는 경우, 최종적으로 원소 1개가 start이자 end이자 mid이다.
    # 여기서 그 다음 단계에서 start와 end의 인덱스가 mid값이 달라짐에 따라 역전이 되게 되는데, 이때 no를 출력하면 된다.
    if start > end:
        return "no"
    # mid의 인덱스는 시작점과 끝점의 중간.
    mid = (start + end)//2
    # 중간점과 찾는 원소가 같다면 yes출력
    if array[mid] == target:
        return 'yes'
    # 찾는 원소가 중간점보다 더 크다면 오른쪽찾기(정수만 있음)
    elif array[mid] < target:
        return (binary_search(array,target,mid+1,end))
        
    # 찾는 원소가 중간점보다 더 작다면 왼쪽찾기(정수만 있음)
    else:
        return (binary_search(array,target,start,mid-1))
    
# 입력받기
n = int(input())
n_list = list(map(int,input().split()))
n_list = sorted(n_list)
m = int(input())
m_list = list(map(int,input().split()))
 
for target in m_list:
    print(binary_search(n_list,target,0,n-1))

풀이: 원하는 숫자를 찾는 문제이므로 탐색방법을 사용해야 하는데 이진 탐색을 사용하였습니다. 여기서 이진 탐색은 시작점, 끝점, 중간점에 대한 개념이 필요합니다.
함수를 만들 때 array, target, start,end를 잡고 mid의 인덱스를 start와 end를 기준으로 정합니다.
그 다음 이진 탐색의 자료구조처럼 탐색을 합니다. 여기서 찾는 원소가 없을 경우가 중요합니다.
이때 결국 최종적으로 1개의 원소만 남게 되고 이 원소랑 찾는 원소랑 다를 경우, return 값에서 mid값에 +-1이 되기 때문에 start와 end로 인덱스가 들어갈 때 start의 인덱스가 2, end의 인덱스가 1이 되는 경우가 생깁니다. 이때 'no'를 출력시키면 됩니다.
또한, 중요한 것은 이진 탐색은 정렬된 리스트에서 사용해야 하므로 원소의 리스트를 입력받고 난 다음에 정렬시켜줘야 합니다.

배운 점: 이진 탐색이라는 것을 아예 몰랐다면 원소를 1개씩 꺼내서 이중 for문으로 문제를 해결 했을 것 같다. 하지만 이진 탐색의 자료구조를 배우니깐 각각의 과정을 머릿속에서 계산할 필요없이 필요한 과정만 생각하면되서 훨씬 효율적인 풀이 이 방법인 것같다. 

- 계수 정렬 사용

# 부품 갯수 입력
n = int(input())
#빈리스트 생성 (조건에서 10만개)
array = [0]*100000
#가게에 있는 전체 부품 번호를 입력받아서 기록
for i in input().split():
    array[int(i)] = 1
print(array)
# 손님의 갯수와 부품번호받기
m = int(input())
m_list = list(map(int,input().split()))
print(m_list)
for i in m_list:
    if array[i] ==1:
        print("yes", end= " ")
    else:
        print("no", end= " ")

-  set() 함수 사용

# 부품 갯수 입력
n = int(input())
#빈리스트 생성 (조건에서 10만개)
n_list = set(map(int,input().split()))
# 손님의 갯수와 부품번호받기
m = int(input())
m_list = list(map(int,input().split()))
 
for i in m_list:
    if i in n_list:
        print("yes", end= " ")
    else:
        print("no", end= " ")

위의 방법도 참고용으로 알면 좋습니다.

<3> 떡볶이 떡 만들기
예를 들어 떡볶이의 떡 높이가 19, 14,10,17cm인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15,14,10,15cm가 될 것이다. 잘린 떡의 길이는 차례대로 4,0,0,2cm이다. 손님은 6cm만큼의 길이를 가져간다.
손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오
(떡의 개수 N, 손님이 요청한 떡의 길이 M, (1<=N<=1,000,000  1<=M<=2,000,000,000)

입력예시)
4 6
19 15 10 17

출력 예시)
15

#입력받기
n,m = map(int, input().split())
#떡 길이 받기
array = list(map(int, input().split()))
array = sorted(array)
# 떡의 시작점은 0, 끝점을 제일 긴값으로 한다.
def binary_search(array,target,start,end):
    # 뒤에 소수점을 버리므로 원하는 값이 없었을 때, 자르는 값인 mid값이 덜 자르는 값이 되버린다.
    mid = (start+end)//2
    if start > end:
        print("1")
        return mid
    
    all_rest_sum = 0
    for i in array:
        if i > mid:
            all_rest_sum += i-mid
    # target이 남는 총합과 같다면 자르는 mid값을 출력
    if all_rest_sum == target:
        print("2")
        return mid
    # target이 남는 총합보다 작다면 더 오른쪽 이동(더 많이 잘라야함)
    elif all_rest_sum > target:
        print("3")
        return binary_search(array,target,mid+1,end)
    # target이 남는 총합보다 크다면 더 오른쪽 이동(더 적게 잘라야함)
    else:
        print("4")
        return binary_search(array,target,start,mid-1)
 
print(binary_search(array,m,0,max(array)))

풀이: 이진 탐색으로 풀기는 했지만 이 문제에서는 인덱스로 접근하는 것이 아니라 값으로 접근하기 때문에 정렬할 필요가 없습니다. 그래서 start와 end도 인덱스가 아니라 값으로 접근합니다. 여기서 핵심은 원하는 값으로 잘라지지 않을 때 해당하는 값보다 덜 자르는 것입니다. 그래서 자르는 값인 mid에서 (start+end)/2과정에서 소수점이 버려지므로 자동적으로 덜 잘라지는 값으로 결정되게 됩니다.

배운 점: 이 문제를 풀 때 원하는 값이 안 나올 때 어떻게 출력해야 할지에 대해 사실 상 엄청 고민을 많이 했다. 예를 들어 원하는 총합이 7일 때, 자르는 값이 14이면, 총합이 8, 자르는 값이 15이면 총합이 6이라면 mid값을 start와 end가 1개의 값이 되는 순간이 오고 난 다음 start와 end를 어떻게 건들여야 할지 쉽게 결정이 나지 않았다. 여기서 mid는 덜 자르는 방향으로 결정해야한다. 그때 결국 한 개의 숫자로 start와 end가 정해질 때 target보다 크다면 더 잘라야 하고 작다면 덜 잘라야 한다. 거기서 어찌 됬든 +-1이 될 것이고 / 2를 한다음에 소수점을 버려버리면 어차피 덜 잘라지게 되는 셈이다. 
ex)
start,end,mid =15 -> total=6
start,end,mid =14 -> total=9
원하는 total=7일때 start,end가 14라면-> (total > target) => start,end(14,14)->(15,14)
원하는 total=7일때 start,end가 15라면-> (total < target) => start,end(15,15)->(15,14) 가 되서 결국 같은 값으로 되기 때문에 /2만 하면 덜 잘려지는 14가 된다.  

- 재귀함수가 아닌 for문을 이용한 풀이

n,m= list(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:
        end =  mid -1
    else:
        # 최대한 덜 랐을 때가 정답이므로 여기서 result에 기록
        result = mid
        start = mid + 1
        
print(result)