Python 알고리즘 공부 (6: 이진탐색)

오늘은 이진탐색에 대해서 알아보았다.

 

 

순차탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 (가장 기본적인 방법)

이진탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 (시작점, 끝점, 중간점 이용하여 탐색범위를 설정한다)

 

 

 

이진탐색을 진행할 때, 우선 순서대로 정렬된 리스트에서 시작점, 중간점, 끝점을 지정한다. 그 후, 찾고자하는 값을 중간점의 값과 비교하여 찾고자하는 값이 중간점을 기준으로 왼쪽에 있는지 오른쪽에 있는지 알아본다. 이러한 방식으로 범위를 절반으로 줄인 뒤, 위 과정을 반복하는 것이다. 이진탐색의 시간복잡도는 log N 을 보장한다. 

 

 

 

코드로 확인하자면, 아래와 같이 적어줄 수 있다.

 

 

 

재귀함수 사용 코드:

# 이진 탐색 소스코드 구현 (재귀 함수)
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)

# n(원소의 개수)과 target(찾고자 하는 값)을 입력 받기
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)

 

 

 

반복문 사용 코드:

# 이진 탐색 소스코드 구현 (반복문)
def binary_search(start, end):
    while start <= end:
        mid = (start + end) // 2
        # 찾은 경우 중간점 인덱스 반환
        if array[mid] == target:
            return mid
        # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
        elif array[mid] > target:
            end = mid - 1
        # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
        else:
            start = mid + 1
    return None

# n(원소의 개수)과 target(찾고자 하는 값)을 입력 받기
n, target = list(map(int, input().split()))
# 전체 원소 입력 받기
array = list(map(int, input().split()))

# 이진 탐색 수행 결과 출력
result = binary_search(0, n - 1)
if result == None:
    print("원소가 존재하지 않습니다.")
else:
    print(result + 1)

 

 

 

파이썬에서는 위와 같이 직접 구현할 필요없이, 이진탐색 라이브러리를 사용할 수 있다. bisect 라는 기본 모듈에서 bisect_left, bisect_right 라는 메서드를 import 해와서 사용할 수 있다. 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))

 

 

 

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

 

 

 

 

문제 1.
오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다. 절단기의 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다. 이걸 처리 안 해줘서 시간을 허비했다.
예를 들어 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것이다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm이다. 손님은 6cm만큼의 길이를 가져간다.
손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

 

 

풀이 1.

위 문제는 이진탐색 코드를 활용하여 해결할 수 있다. 설정하는 길이 값을 이진탐색을 활용하여 계속해서 최적화시켜나가는 것이다. 아래와 같은 코드로 해결한다.

 

 

 

# n 은 떡의 개수
# m 은 요청한 떡의 길이

n, m = map(int, input().split())
array = list(map(int, input().split()))
# array.sort()

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)

 

 

 

 

 

 

Reference:

이것이 취업을 위한 코딩 테스트다