[Week02] 알고리즘 - 이분탐색

[Week02] 알고리즘 키워드 - 이분탐색, 분할정복, 스택, 큐, 우선순위 큐

검색 알고리즘 - 선형탐색 / 이분 탐색

이분탐색

정렬이 되어있는 배열에서 특정 데이터를 찾기 위해서 모든 데이터를 순차적으로 확인하는 대신 탐색의 범위를 절반으로 줄여나가는 탐색 방법

 

이분탐색 사용시 주의사항

1. 주어진 배열은 정렬되어있어야한다.
2. 무한 루프에 빠지지않게 mid값을 잘 지정해준다

차례로 증가(혹은 감소)시키면서 풀어야하는 탐색문제에 큰 수의 범위가 주어진다면 이분탐색을 떠올려보자.

시간복잡도 O(logN)

 

✅ 이분탐색 구현하기

while문을 이용하여 구현

def binary_serch(a,n_list) :
    st = 0
    en = n-1
    while st <= en :
        mid = (en+st)//2
        if n_list[mid] == a :
            return True
        elif n_list[mid] > a :
            en = mid -1
        else :
            st = mid + 1
    return False

 

✅ 이분탐색 모듈 - bisect

• bisect_left(alist, x) : 정렬된 list에 x를 삽입할 위치를 리턴한다. x가 있는 경우 x의 인덱스를 리턴한다.
• bisect_right(alist, x) : 정렬 list에 x를 삽입할 위치를 리턴한다. x가 있는 경우 오른쪽 인덱스를 리턴한다. 

from bisect import bisect_left, bisect_right

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

print(bisect_left(a, target))     # 2
print(bisect_right(a, target))    # 4

이분탐색

import bisect
def binary_search(array, target):
    index = bisect.bisect_left(array, target)
    if index < len(array) and array[index] == target:
        return index
    #index가 len(array)와 같거나 0일 경우 해당 list에 target이 없다. 
    return False

 

모듈을 이용하여 중복이 있을 경우 범위를 구할 수 있다❕ 

 

✅ 파라메트릭 서치

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

문제의 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제를 이분탐색으로 결정문제를 해결하면서 탐색 범위를 좁혀갈 수 있다. 

 

#백준2805

적당한 길이를 찾을때까지 길이를 반복해서 조절한다. 그 후 '현재 크기면 조건을 만족하는가'를 확인한 뒤 만족 여부에 따라 범위를 좁혀간다.

import sys

n,m = map(int,sys.stdin.readline().split())
trees = list(map(int,sys.stdin.readline().split()))

trees.sort()

#start,end 변수를 인덱스값이 아닌 데이터 값을 담는다. 
start = 1
end = max(trees)

#target이 주어지지않고 구하는 것이 목적이기때문에 mid변수를 이용하는 형태
while start <= end :
    mid = (start+end)//2
    sum0 = [tree-mid if tree > mid else 0 for tree in trees]
    sum_value = sum(sum0)
    if sum_value >= m :
        start = mid + 1
    else : 
        end = mid - 1

print(end)

 

파라메트릭 서치 유형의 문제 근거

1. 결정 문제를 정의 했을 때, 쉽게 풀 수 있는 경우

2. 가능한 해의 영역이 연속적이여야 한다. (감소함수이거나 증가함수여야한다.)

 

 

열코하세용 🏹