이 영상을 보며 작성하였습니다.
이진 탐색: 시작점, 끝점, 중간점의 위치를 나타내는 변수 3개를 이용함. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 방법.
#이진 탐색 소스코드 구현 (재귀 함수)
def binary_search(array,targrt,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(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
from bisect import bisect_left, bisect_right
bisect_left(a,x): 정렬된 순서를 유지하면서, 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환.
bisect_right(a,x): 정렬된 순서를 유지하면서, 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환.
# 값이 특정 범위에 속하는 데이터 개수 구하기
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 = […,…,…] #배열 선언
파라메트릭 서치: 최적화 문제를 결정 문제(‘예’ 혹은 ‘아니오’)로 바꾸어 해결하는 기법 (특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제). 일반적으로 코딩 테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결할 수 있음
728x90
'파이썬 알고리즘 문제 풀이' 카테고리의 다른 글
Baekjoon Online Judge 2805번 파이썬 (1) | 2022.09.19 |
---|---|
Baekjoon Online Judge 1654번 파이썬 (0) | 2022.09.14 |
Baekjoon Online Judge 1967번 파이썬 (1) | 2022.09.07 |
Baekjoon Online Judge 1167번 파이썬 (0) | 2022.09.04 |
Baekjoon Online Judge 11725번 파이썬 (0) | 2022.09.01 |