이진 탐색 알고리즘: 정렬되어 있는 리스트에서 특정한 데이터를 빠르게 탐색할 수 있도록 해주는 알고리즘
순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 (단순히 데이터를 하나씩 확인하는 것)
이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 (리스트가 정렬되어 있을 때 사용 가능), 로그 시간의 시간복잡도를 가질 수 있음
이진 탐색 동작 예시
시작점, 중간점, 끝점: 인덱스
찾으려는 값과 중간점 값을 비교 (중간점 값이 더 크면 중간점 오른쪽 값은 확인할 필요 없음)
끝점을 중간점의 왼쪽으로 옮김
다시 중간점을 찾고, 중간점 값보다 찾으려는 값이 더 크기에 중간점 왼쪽 데이터는 버림
시작점 위치를 중간점 오른쪽으로 옮겨줌
중간점위치의 값이 찾고자하는 값과 동일하기에 탐색을 마침
이진 탐색의 시간 복잡도
코드: 재귀적 구현
# 이진 탐색 소스코드 구현 (재귀 함수)
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)
# 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
elif array[mid] < target:
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) #인덱스값에 1을 더해 몇번째인지 프린트함
코드: 반복문 구현
# 이진 탐색 소스코드 구현 (반복문)
def binary_search(array, target, start, end):
while start <= end:
mid = (start + end) // 2
# 찾은 경우 중간점 인덱스 반환
if array[mid] == target:
return mid
# 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
elif array[mid] > target:
end = mid -1
# 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
elif array[mid] < target:
start = mid + 1
return None
# 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) #인덱스값에 1을 더해 몇번째인지 프린트함
파이썬 이진 탐색 라이브러리
bisect_left(a,x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환
bisect_right(a,x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환
값이 특정 범위에 속하는 데이터 개수 구하기
bisect right을 통해 구한 값과 bisect left를 통해 구한 값을 빼주면 해당 값의 범위에 포함되어 있는 데이터의 개수를 구할 수 있음
from bisect import bisect_left, bisect_right
# 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
def count_by_range(a, left_value, right_value):
right_index = bisect_right(a, right_value)
left_index = bisect_left(a, left_value)
return right_index - left_index
# 배열 선언
a = [1,2,3,3,3,3,4,4,8,9]
# 값이 4인 데이터 개수 출력
print(count_by_range(a,4,4))
# 값이 [-1,3] 범위에 있는 데이터 개수 출력
print(count_by_range(a,-1,3))
# 실행 결과: 2, 6
파라메트릭 서치 (Parametric Search)
문제 해결 아이디어
조건을 만족하므로 현재의 높이값 기록(저장)
이와 같이 이진탐색을 수행해서 더이상 탐색범위를 줄어들지 못하게 할 때까지 시작점과 끝점의 위치를 바꾸어 가면서 높이값을 매번 바꾸어보며 현재의 높이로 잘랐을 때 조건을 만족할 수 있는지를 체크하는 방식으로 답을 구함
현재의 높이에서 잘랐을 때 필요한 떡의 크기 이상의 떡을 얻을 수 있다면 그때마다 결과를 기록해서 최종적으로 이진탐색을 더이상 수행할 수 없을때까지 반복했을 때 기록되어 있는 그 결과값을 출력하게 만듦 → 그 결과값이 최적의 높이값
이러한 이진 탐색 과정을 반복하면 답을 도출할 수 있음
중간점의 값은 시간이 지날수록 ‘최적화된 값'이 되기 때문에, 과정을 반복하면서 얻을 수 있는 떡의 길이 합이 필요한 떡의 길이보다 크거나 같을 때마다 중간점의 값을 기록하면 됨
코드
# 떡의 개수(N)와 요청한 떡의 길이(M)를 입력
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 # 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록
start = mid + 1
# 정답 출력
print(result)
문제 해결 아이디어
시간 복잡도 O(logN)으로 동작하는 알고리즘을 요구하고 있기에
특정 값이 등장하는 첫번째 위치와 마지막 위치를 찾아 위치 차이를 계산해 문제 해결
처음 전체 탐색 범위에 대해서 이진 탐색을 두번 수행하여 하나는 첫 위치를, 다른 하나는 마지막 위치를 찾도록 만들어서 문제 해결
이진탐색을 직접 구현하거나 표준 라이브러리(bisect_left, bisect_right)이용
코드
from bisect import bisect_left, bisect_right
# 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
def count_by_range(a, left_value, right_value):
right_index = bisect_right(a, right_value)
left_index = bisect_left(a, left_value)
return right_index - left_index
n, x = map(int, input().split()) # 데이터의 개수 N, 찾고자 하는 값 x 입력받기
array = list(map(int, input().split())) # 전체 데이터 입력받기
# 값이 [x,x] 범위에 있는 데이터의 개수 계산
count = count_by_range(array, x, x)
# 값이 x인 원소가 존재하지 않는다면
if count == 0:
print(-1)
# 값이 x인 원소가 존재한다면
else:
print(count)
참고: 이것이 취업을 위한 코딩 테스트다 with 파이썬 (취업과 이직을 결정하는 알고리즘 인터뷰 완벽 가이드), 유튜브 강의 영상