[이것이코딩테스트다/이코테] CH7 이진탐색 python (+연습문제, 예시답안)

이진 탐색 알고리즘

• 정렬되어 있는 리스트에서 탐색 범위 좁히면서 하나씩 → 시작점, 끝점, 중간점을 이용하여 탐색 범위 좁혀나감
• 단계마다 탐색 범위를 2로 나누는 것과 동일해서 연산 횟수는 log2N에 비례 → 시간복잡도: O(logN)

활용 파이썬 라이브러리

from bisect import bisect_left, bisect_right

bisect_left(a, x) : 배열 a에 v를 삽입할 가장 왼쪽 인덱스 반환

bisect_right(a, x) : 배열 a에 v를 삽입할 가장 오른쪽 인덱스 반환

→ 값이 특정 범위에 속하는 데이터 개수를 구할 수 있음.

 

파라메트릭 서치

• 최적화 문제를 결정문제(yes or no)로 바꾸어 해결하는 기법

ex. 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제

• 파라메트릭 서치 문제는 이진 탐색을 이용해 해결 가능

 

---

문제1. 떡볶이 떡 만들기

문제: 떡볶이의 떡은 길이가 일정하지 않음. 대신 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰줌. 절단기에 높이(H)를 지정하면 떡을 절단하여 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고 짧은 떡은 잘리지 않을 것임. 예를 들어 높이가 19, 14, 10인 떡이 있을 때 절단기 높이를 15로 지정하면 자른 떡의 높이는 15, 14, 10이 될 것이고 잘린 떡의 길이는 차례대로 4, 0, 0일 것으로 손님은 4만큼의 길이를 가져감. 손님이 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 설정할 수 있는 H의 최댓값을 구하는 프로그램을 작성하시오. 떡 개수(N), 떡의 길이(M), 떡의 개별 높이들이 주어짐. 

 

예제 결과🙆🏻‍♀️

입력: N = 4, M = 6, [19, 15, 10, 17] / 출력: 15

 

# 1차 시도
ttuk_list = [19, 15, 10, 17]
ttuk_list.sort()

def binary(array, height, mid, end):
    total = 0
    end_revise = end
    while total < M:
        if height <= max(array[:mid]):
            mid -= 1
        h_list = list(map(lambda x:abs(height-x), ttuk_list[mid:end_revise+1]))
        if sum(h_list) <= M:
            height -= 1
            total = sum(h_list) + total + (end-end_revise)
            end_revise -= 1
    return height

mid = len(ttuk_list) // 2
height = ttuk_list[mid]
end = len(ttuk_list)
binary(ttuk_list, height, mid, end)

 

문제점: 쓸데없이 비교하는 경우도 많음 -> 더 빠르게 가능

시작점, 끝점, 중간점을 설정 -> 끝점을 리스트의 max로 설정

 

# 2차 시도
N = 4
M = 6

ttuk_list = [19, 15, 10, 17]

def binary(array, start, end):
    total = 0
    mid = (start + end) // 2
    while total <= M:
        total = 0
        h_list = list(map(lambda x: x-mid, [y for y in array if y > mid]))
        if sum(h_list) > M:
            start = mid
            mid = (start + end) // 2
        elif sum(h_list) < M:
            mid = (start + mid) // 2
        else:
            total = sum(h_list)
            break

    return mid

end = max(ttuk_list)
start = 0
binary(ttuk_list, start, end)

 

문제점: 리스트에 있는 값들로만 비교 가능

---

예시 답안

N = 4
M = 6

ttuk_list = [19, 15, 10, 17]

end = max(ttuk_list)
start = 0

result = 0
while start <= end: # 이 조건이 중요
    mid = (start + end) // 2

    h_list = list(map(lambda x: x-mid, [y for y in ttuk_list if y > mid]))
    if sum(h_list) < M:
        end = mid -1
    else:
        result = mid
        start = mid + 1

print(result)

 

< 나와 다른 부분 > ⭐

1) while 조건문과 start를 mid+1로, end를 mid+1로 설정해주는 것이 중요

 

---

문제2. 정렬된 배열에서 특정 수의 개수 구하기

문제: N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있음. 수열에서 x가 등장하는 횟수를 계산해라. 예를 들어 수열 {1,1,2,2,2,2,3}이 있을 때, x=2라면 값이 2인 원소가 4개이므로 4를 출력.

 

예제 결과🙆🏻‍♀️
입력: N=7, x=2, 수열: {1, 1, 2, 2, 2, 2, 3} / 출력: 4
* 단, 해당 문제는 시간 복잡도를 O(logN)으로 설계하지 않으면 시간 초과 판정을 받음

 

 

💡Idea: bisect 라이브러리를 사용하여 값이 있는 마지막 인덱스에서 처음 인덱스를 빼줌

# 1차 시도
N = 7
x = 2
array = [1,1,2,2,2,2,3]

from bisect import bisect_left, bisect_right

result = bisect_right(array, x) - bisect_left(array, x)
if result == 0:
    print(-1)
else:
    print(result)