I about me

[이것이 코딩테스트다] 5. 이진 탐색 본문

Algorithm/이것이 코딩테스트다!

[이것이 코딩테스트다] 5. 이진 탐색

ssungni 2024. 7. 22. 22:14

해당 강의를 참고하여 공부를 진행했습니다.

https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC


이진 탐색 동작 예시

  • 정렬된 데이터 중에서 특정 원소를 찾는 과정
  • 시작점, 끝점, 중간점: 4 (소수점 이하 제거)
  • 시간복잡도 O(log N)
  • ex)

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)

# target : 찾고자 하는 값
n, target = list(map(int, input().split())) # 10, 7
array = list(map(int, input().split())) # 1 3 5 !!7!! 9 11 13 15 17 19

result = binary_search(array, target, 0, n - 1)
if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result + 1) # 인덱스는 3이지만 4번째 원소이므로 결과값 4가 나옴

이진 탐색 라이브러리

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

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

print(bisect_left(a, 3)) # [1, 2, 3, 4, 5, 8]
print(bisect_right(a, 6)) # [1, 2, 3, 4, 5, 6, 8]

print(a) # 적용이 안 됨

교재 예시 설

a = [1, 2, 4, 4, 8]
x = 4
print(bisect_left(a, x))
print(bisect_right(a, x))

응용

  • 값이 특정 범위에 속하는 데이터 갯수
from bisect import bisect_left, bisect_right

def count_by_range(a, left_value, right_value):
    left_index = bisect_left(a, left_value)
    right_index = bisect_right(a, right_value)
    return right_index - left_index

a = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9]

print(count_by_range(a, 3, 3)) # 4

# 값이 [-1, 3] 범위에 있는 데이터 개수 출력
print(count_by_range(a, -1, 3)) # 6

파라메트릭 서치

  • 파라메트릭 서치란 최적화 문제를 결정 문제(예 혹은 아니오)로 바꾸어 해결하는 기법
    • ex) 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제
  • 일반적으로 코딩 테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결할 수 있다

<문제>

떡복이 떡 만들기

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 = mid
        start = mid + 1

print(result)

 

정렬된 배열에서 특정 수의 개수 구하기

from bisect import bisect_left, bisect_right

def count_by_range(a, left_value, right_value):
    left_index = bisect_left(a, left_value)
    right_index = bisect_right(a, right_value)
    return right_index - left_index

n, x = list(map(int, input().split())) # 7 2
array = list(map(int, input().split())) # 1 1 2 2 2 2 3

# print(count_by_range(array, x, x)) # 4

count = count_by_range(array, x, x)

if count == 0:
    print(-1)
else:
    print(count)