[알고리즘 대비 - 이코테] 6. 이진 탐색

개념

• 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법
• 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
  • 정렬된 리스트에서만 사용이 가능하다.
  • 시간복잡도는 O(lg n) 을 갖는다.
  • 보통 시작점, 중간점, 끝점을 갖는 변수를 할당하여 값을 구한다.

💡 탐색 범위가 2,000만을 넘어가면 이진 탐색으로 접근해보자!

---

동작원리

• 중간점과 찾는 값을 비교하여 중간점을 기준으로 오른쪽(찾는 값이 더 큰 경우)에 있는 지, 왼쪽(찾는 값이 더 작은 경우)에 있는 지 비교한다.
• 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 lg N에 비례한다. 시간복잡도 : O(lg N)

 

이진 탐색(재귀)

def binary_search(arr, tar, start, end):
    # tar 값이 없는 경우
    if start > end:
        return None
    mid = (start + end) // 2
    # tar 값을 찾은 경우
    if arr[mid] == tar:
        return mid
    # mid 값보다 tar 값이 작은 경우
    elif arr[mid] > tar:
        return binary_search(arr, tar, start, mid-1)
    # mid 값보다 tar 값이 큰 경우
    else:
        return binary_search(arr, tar, mid+1, end)

---

이진 탐색(반복문)

def binary_search(arr, tar, start, end):
    while start <= end:
        mid = (start + end) // 2
        # tar 값을 찾은 경우
        if arr[mid] == tar:
            return mid
        # mid 값보다 tar 값이 작은 경우
        elif arr[mid] > tar:
            end = mid - 1
        # mid 값보다 tar 값이 큰 경우
        else:
            start = mid + 1
    # tar 값이 없는 경우
    return None

---

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

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

from bisect import bisect_left, bisect_right

a = [1, 2, 4, 4, 8]
x = 4

print(bisect_left(a, x))
print(bisect_right(a, x))

'''
Result

> 2
> 4
'''

---

파라메트릭 서치(Parametric Search)

• 최적화 문제를 결정 문제(예 혹은 아니오 )로 바꾸어 해결하는 기법이다.
• 일반적으로 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결할 수 있다.

---

Q1. 부품 찾기

문제 설명

동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자.

입력 조건

• 첫째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 1,000,000)
• 둘째 줄에는 공백으로 구분하여 N개의 정수가 주어진다. 이때 정수는 1보다 크고 1,000,000 이하 이다.
• 셋째 줄에는 정수 M이 주어진다. (1 ≤ M ≤ 100,000)
• 넷째 줄에는 공백으로 구분하여 M개의 정수가 주어진다. 이때 정수는 1보다 크고 1,000,000 이하이다.

출력 조건

• 첫째 줄에 공백으로 구분하여 각 부품이 존재하면 yes를, 없으면 no를 출력한다.

풀이

from sys import stdin
n = int(stdin.readline())
arr_n = list(map(int, stdin.readline().split()))
m = int(stdin.readline())
arr_m = list(map(int, stdin.readline().split()))

arr_n.sort()  # 이진 탐색을 위해 리스트 정렬
arr_m.sort()
start = 0

for i in arr_m:
    target = i
    flag = 0
    end = n - 1
    while start <= end:
        mid = (start + end) // 2
        if arr_n[mid] == target: # 일치하는 값 찾은 경우 반복문 탈출
            flag = 1
            break
        elif arr_n[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    if flag: # 일치하는 값을 찾은 경우에만 'yes'출력
        print('yes ', end='')
    else:
        print('no ', end='')

• arr_m 리스트를 정렬하여 이전 탐색 이후의 범위에서만 탐색을 진행한다.
  • 다시 start 값을 갱신할 필요 ❌
  • Ex. 이전 반복문의 target 값이 4, arr_n[start] 값이 2 이고
  • 현재 반복문의 target 값이 6, 일 경우, 굳이 다시 start 값을 0 으로 초기화할 필요가 없다. (불필요한 코드 수행 최소화)

 

---

Q2. 떡볶이 떡 만들기

문제 설명

오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다.

절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다.

예를 들어 높이가 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)
• 둘째 줄에는 떡의 개별 높이가 주어진다. 떡 높이의 총합은 항상 M 이상이므로, 손님은 필요한 양만큼 떡을 사갈 수 있다. 높이는 10억보다 작거나 같은 양의 정수 또는 0이다.

출력 조건

• 적어도 M만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

풀이

from sys import stdin
n, m = map(int, stdin.readline().split())
arr = list(map(int, stdin.readline().split()))

start, end = 0, max(arr)
while start <= end:
    rst = 0
    target = (start + end) // 2
    for i in arr:
        if i > target:
            rst += i - target
    if rst == m:
        break
    elif rst < m:
        end = target - 1
    else:
        start = target + 1
print(target)

• 파라메트릭 서치 문제로, 이진 탐색으로 결정 문제를 해결한다.
• while 문이 끝날 때, rst 의 값은 가장 최적화된 상태로 끝나게 된다.
• 자른 떡의 총합이 m이 될 경우가 가장 최적의 경우이므로 rst == m 을 충족할 경우 반복문을 탈출한다.

 

---

해당 포스팅의 내용은
저)나동빈님의 『이것이 취업을 위한 코딩 테스트다 with 파이썬』을
통해 공부한 내용을 토대로 작성하였습니다.

이것이 취업을 위한 코딩 테스트다 with 파이썬
저자 | 나동빈
출판 | 한빛미디어
발매 | 2020.08.05.