- 이것이 취업을 위한 코딩테스다 with 파이썬(이코테 2021) 유튜브 영상을 보면서 공부한 자료입니다.
- https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC
이진 탐색 알고리즘
- 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해, 앞에서부터 데이터를 하나씩 확인하는 방법
- 이진 탐색 : 정렬되어 있는 리스트에서, 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
- 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다.
입력 예시
10 7
1 3 5 7 9 11 13 15 17 19
- 배열의 개수 N, 찾고자 하는 target이 순서대로 입력된다.
- 배열이 공백으로 구분하여 입력된다(오름 차순 정렬).
출력 예시
4
- 배열에서, target을 찾아 해당하는 인덱스를 반환한다.
- target이 존재하지 않는 경우, -1을 출력한다.
def binary_search(arr, target, start, end):
if start > end:
return None
mid = (start + end) // 2
if arr[mid] == target:
return mid
elif arr[mid] > target:
end = mid - 1
elif arr[mid] < target:
start = mid + 1
return binary_search(arr, target, start, end)
n, target = map(int, input().split())
arr = list(map(int, input().split()))
res = binary_search(arr, target, 0, n - 1)
if res is None:
print(-1)
else:
print(res + 1)
이진 탐색의 시간 복잡도
- 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 다음과 같다.
- 따라서 시간 복잡도는 다음과 같다.
파이썬 이진 탐색 라이브러리
- bisect_left(a, x): 정렬된 순서를 유지하면서, 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환
- bisect_right(a, x): 정렬된 순서를 유지하면서, 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환
from bisect import bisect_left, bisect_right
arr = [1, 2, 4, 4, 8]
target = 4
print(bisect_left(arr, target))
print(bisect_right(arr, target))
<문제 1> 값이 특정 범위에 속하는 데이터 구하기
입력 예시
1 2 3 3 3 3 4 4 8 9
4
- 첫번재 줄에 배열이 주어진다.
- 두번째 줄에 배열에서 찾고자 하는 target이 주어진다.
출력 예시
2
- 해당 배열에서 target이 존재하는 횟수를 출력한다.
from bisect import bisect_left, bisect_right
def count_by_range(arr, left_val, right_val):
left_idx = bisect_left(arr, left_val)
right_idx = bisect_right(arr, right_val)
return right_idx - left_idx
arr = list(map(int, input().split()))
target = int(input())
res = count_by_range(arr, target, target)
print(res)
파라메트릭 서치(Parametric Search)
- 파라메트릭 서치란, 최적화 문제를 결정 문제('예' 혹은 '아니오')로 바꾸어 해결하는 기법이다.
- 예시 : 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제 - 일반적으로 코딩 테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결할 수 있습니다.
<문제 2> 떡볶이 떡 만들기
입력 예시
4 6
19 15 10 17
- 첫째 줄에 떡의 개수 N과, 요청한 떡의 길이 M이 주어진다.
- 둘째 줄에는 떡의 개별 높이가 주어진다. 떡 높이의 총합은 항상 M이상이므로, 손님은 필요한 양만큼 떡을 사갈 수 있다.
출력 예시
15
- 적어도 M만큼의 떡을 집에 가져가기 위해, 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.
<풀이 2> 떡볶이 떡 만들기
문제 해결 아이디어
- 적절한 높이를 찾을 때까지 이진 탐색을 수행하여 높이 H를 반복해서 조정하면 된다.
- "현재 이 높이로 자르면 조건을 만족할 수 있는가?"를 확인한 뒤에, 조건의 만족 여부를 "예" 혹은 "아니오"에 따라서 탐색 범위를 좁혀서 해결할 수 있다 -> 이진 탐색으로 해결 가능
- 0부터 10억까지 등의 큰 탐색 범위를 보면, 가장 먼저 이진 탐색을 떠올려야 한다.
n, m = map(int, input().split())
arr = list(map(int, input().split()))
start = 0
end = max(arr)
res = 0
while start <= end:
mid = (start + end) // 2
total = 0
for a in arr:
if a > mid:
total += (a - mid)
if total >= m:
res = mid
start = mid + 1
else:
end = mid - 1
print(res)
<문제 3> 정렬된 배열에서 특정 수의 개수 구하기
입력 예시
7 2
1 1 2 2 2 2 3
- 첫째 줄에 N과 X가 정수 형태로 공백으로 구분되어 입력된다.
- 둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력된다.
출력 예시
4
- 수열의 원소 중에서 값이 x인 원소의 개수를 출력한다. 단 값이 x인 원소가 하나도 없다면, -1을 출력한다.
<풀이 3> 정렬된 배열에서 특정 수의 개수 구하기
문제 해결 아이디어
- 데이터가 정렬되어 있기 때문에, 이진 탐색을 수행할 수 있다.
- 특정 값이 등장하는 첫 번째 위치와, 마지막 위치를 찾아 위치 차이를 계산해 문제를 해결한다.
from bisect import bisect_left, bisect_right
def count_by_range(arr, left_val, right_val):
left_idx = bisect_left(arr, left_val)
right_idx = bisect_right(arr, right_val)
return right_idx - left_idx
n, x = map(int, input().split())
arr = list(map(int, input().split()))
res = count_by_range(arr, x, x)
if res == 0:
print(-1)
else:
print(res)
- count_by_range 함수는 유용한 면이 많으니, 암기하여 사용하는 것을 권장한다.
안녕하세요.