이진 탐색
- 반으로 쪼개면서 탐색하는 방법으로, 데이터가 정렬되어 있는 배열에서 사용할 수 있는 알고리즘이다. 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징을 가지고 있다.
- 따라서 위치를 나타내는 변수 3개를 사용하는데 탐색하고자 하는 범위의 시작점, 끝점, 중간점을 변수로 가진다. 이진 탐색은 찾으려는 데이터와 중간점에 있는 데이터를 반복적으로 비교하며 탐색해 나간다.
- 시간 복잡도는 한 단계 거칠 때마다 확인하는 원소가 평균적으로 절반씩 줄어드므로 빅오 표기법에 의해 O(logN)이다.
- 코딩 테스트에서 단골로 나오는 문제이므로 외우는 것을 추천하며 보통 탐색 범위가 큰 상황에서 사용된다. 탐색 범위가 2000만을 넘어가면 이진 탐색 접근을 권한다고 한다.
구현 방법 1 : 재귀 함수
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 = 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) #인덱스는 0부터 시작이므로
구현 방법 2 : 반복문
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
else:
start = mid + 1
return None
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) #인덱스는 0부터 시작이므로
이진 탐색 트리
- 이진 탐색이 동작할 수 있도록 고안된 자료구조이다.
- '왼쪽 자식 노드 < 부모노드 < 오른쪽 자식 노드' 라는 특징을 갖는다.
- 이진 탐색 트리를 구현하는 문제는 출제 빈도가 낮다.
입력 빠르게 받기
- 이진 탐색은 탐색 범위가 매우 넓은 편으로 입력 데이터 또한 많은 편이다.
- 위와 같은 상황에서 input() 함수를 사용하면 동작 속도가 느려 시간 초과로 오답 판정을 받을 수 있다.
- 따라서 sys 라이브러리의 readline() 함수를 이용하면 시간 초과를 피할 수 있다.
import sys
input_data = sys.stdin.readline().rstrip()
print(input_data)
- rstrip() 함수는 공백 문자를 제거하는 함수이다. readling() 함수 사용시 입력 후 엔터가 줄 바꿈 기호로 입력되는데 이를 제거해주기 위함이다.
매개변수 탐색
- 이진 탐색을 바탕으로 조건을 만족하는 최댓값/최솟값을 구하는 탐색 방법이다.
- 이진 탐색은 target을 찾으면 함수를 종료하는 반면, 매개변수 탐색은 target을 찾아도 끝까지 탐색을 한다.
매개변수 탐색 방법
- 정답을 매개 변수로 만들기
- 문제를 결정 문제(Yes/No)로 만들기
- 결정(Yes/No)이 완료되었을 때 정렬 상태인지 확인하기
- 결정이 바뀌는 지점 찾기 (Yes → No or No → Yes)