[python]🔑이진탐색 알고리즘

💢이진탐색

➰이진탐색 개념잡기

• ✅순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법
• ✅이진탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
  • 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정

4를 찾고자 하는 경우라고 생각해보자

✅[step 1]

정렬되어 있는 리스트

[0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

• 시작점: 0(인덱스)-'0'을 의미
• 끝점: 9(인덱스) -'8'을 의미
• 중간점: 4(인덱스,소수점 이하제거) -'18'을 의미

우리가 찾고자하는 숫자 '4'와 인덱스 4의 있는 숫자를 비교했을때 8이 더 클 경우 우리는 8보다 오른쪽에 있는 숫자들은 생각할 필요가없다. 그러면 끝점을 8보다 한 칸 왼쪽에 있는 6으로 지정하고 중간점을 지정해주다

✅[step 2]

[0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

• 시작점: 0(인덱스) -'0'을의미
• 끝점: 3(인덱스) -'6'을의미
• 중간점: 1(인덱스,소수점 이하제거)-'2'를의미

우리가 찾고자하는 숫자는 4이지만 중간점에 있는 2를 가지고 있는 인덱스1보다 왼쪽에 있는 데이터들은 신경쓸 필요가 없다. 그러므로 시작점을 중간점 오른쪽으로 한 칸 이동시켜야할 필요가 있다.

✅[step 3]

0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

• 시작점: 2
• 끝점: 3
• 중간점: 2

시작점과 중간점이 같아졌으므로 우리가 원하는 값을 찾았다. 탐색을 종료하면 된다.

➰이진탐색 시간복잡도

• 단계마다 탐색범위를 2로 나누는것과 동일하므로 연산 횟수는 log2N에 비례
  이진 탐색은 탐색 범위를 절반식 줄이며, 시간 복잡도는 O(logN)을 보장한다

그러면 지금까지 학습한 이진탐색이 코드로 어떤식으로 구현되는 살펴보자

코드

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)

    # 반대로 중간값이 타겟숫자보다 작으면 왼쪽데이터는 볼 필요가 없으므로 시작점을 중간점+1한 위치로 지정
    else:
        return binary_search(array, target, mid+1, end)

n, target = list(map(int, input().split()))
array = list(map(int, input().split()))

result = binary_search(array, target, 0, n-1)

if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result+1)

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

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

[1, 2, 4, 4, 8]
리스트가 위에 같이 있을때 bisect_left(a, 4)를 하게되주면 4라는 값이 들어갈 수 있는 가장 왼쪽에 인덱스 값을 반환해준다. 예를 들어 2와 4사이에 들어갈 수 있으므로 인덱스 2를 반환해준다. 마찬가지고 bisect_right(a, 4)를 하게되면 가장 오른쪽에 들어갈 수 있는(4와 8사이) 인덱스 4를 반환해줄 것이다
코드로 함께 살펴보자!

코드

from bisect import bisect_left, bisect_right

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

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

>>>6 10

위에 코드를 보면 알 수 있듯이 8이 들어갈 수 있는 가장 왼쪽인덱스 값인 6을 반환하고 가장 오른쪽에 들어갈 수 있는 인덱스 값이 10을 반환시키는 것을 알 수 있다.

방금 학습한 라이브러리를 이용하여 특점 범위에 속하는 데이터 개수를 구해보자

코드

# 이진탐색 라이브러리 호출
from bisect import bisect_left, bisect_right

def count_by_range(array, start, end):
    #찾고자 하는 범위 시작부분에 bisect_left를 사용해 시작부분을 지정
    start = bisect_left(array, start)

    #찾고자 하는 범위 끝부분에 bisect_right를 이용해 끝부분을 지정
    end = bisect_right(array, end)

    #end 부분과 start부분을 빼주면 몇개가 존재하는 파악 가능
    return end - start

array = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9]
print(count_by_range(array, 3, 3))
print(count_by_range(array, 1, 3))

해석

• 3이라는 숫자의 개수를 찾고싶을때 범위를 시작부분과 끝부분의 각각 3으로 지정을 해주면 3이 들어갈 수 있는 가장 왼쪽 인덱스 값인 2를, 3이 들어갈 수 있느느 가장 오른쪽 인덱스 값인 6을 뽑아내 6과 2를 빼주면 3의 개수인 4를 구할 수 있다.
• 두 번째는 시작부분에 1을, 끝 부분에 3이라는 범위를 설정해 주었다. 이럴 경우 1이 들어갈 수 있는 가장 왼쪽 인덱스인 0을, 3이 들어갈 수 있는 가장 오른쪽 인덱스 값인 6을 반환해준다.
  6과 0을 빼주면 6이라는 1~3범위의 개수를 구할 수 있다.

➰파라메트릭 서치

• 최적화 문제를 결정문제('예' 혹은 '아니오')로 바꾸어 해결하는 기법
  • 예시 특정한 조건을 만족하는 가장 알맞을 값을 빠르게 찾는 최적화문제
  • 최적화 문제란? 어떤 함수의 값을 가능한 높이거나 낮추는 등의 문제를 의미

<문제-떡볶이 떡 만들기>

<문제설명>

• 떡볶이 떡을 만드려고 한다. 하지만 떡의 길이가 일정하지 않다. 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰야 한다.
• 절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단할 수 있다. 높이가 H보다 긴 떡은 H위의 부분이 잘릴 것이고, 낮은 떡을 잘리지 않을 것이다
• 예를 들어 떡의 높이가 19, 14, 10, 17인 떡을 자를 경우 15, 14, 10, 15 가 되고 잘린떡의 길이는 차례대로 4, 0, 0, 2cm 이고 손님이 가져가게 되는 떡은 6cm가 된다
• 손님이 왔을 때 요청한 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오

[step 1]

잘린떡의 길이는 10, 6, 1, 8 로 25이다. 손님이 요구했던 6보다 훨씬 더 많은므로 시작지점 중간 + 1로 변경하여 다시 이진탐색을 시행한다.

[step 2]

잘린떡의 길이는 5, 1, 3으로 총 길이는 9이다. 손님이 요청한 떡의 길이보다 많으므로 시작점을 다시 중간지점에 +1한 위치로 변경해준다.

[step 3]

잘린떡의 길이는 2밖에 되지않아 손님이 요구했던 6만큼 충족시키지 못했다. 따라서 끝점을 중간 -1한 값을 적용시킨다.

[step 4]

잘린떡의 길이는 정확히 6이되며 손님이 요구했던 조건을 만족시켰다는것을 확인할 수 있다.

위와 같은 상황을 코드로 구현해 보자

코드

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)

학습자료 참고 : https://www.youtube.com/watch?v=94RC-DsGMLo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=6