-
[알고리즘] 이진 탐색 정리알고리즘 2022. 9. 16. 15:02728x90
이진탐색 - 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 탐색
- 시작, 끝, 중간점이 있음
- 중간점은 소수점 이하 제거한 값 ( 중간이 명확히 안나눠지는경우 )
- 리스트가 정렬이 되어 있어야만하다
- O(logN)
- 순차 탐색은 데이터를 앞에서부터 탐색함 ( 이진과는 다름 )
#재귀 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) #반복문 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())) res = binary_search(array,target,0,n-1) if res == None: print("원소 존재하지 않음") else: print(res + 1) #인덱스 값이므로 res + 1을 해줘야 한다
파이썬 이진 탐색 라이브러리
파라메트릭 서치
- 이진 탐색 사용
- 최적화 문제 → 결정문제 형태를 바꾸어 해결 ( 결정문제는 예 or 아니오 로 바꿔 해결하는 방법 )
- 특정 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제
- 탐색 범위가 너무 크면 이진탐색을 생각해야 한다.
문제1) 떡볶이 떡 만들기
수행과정
- 떡볶이의 길이는 절단기로 일정하게 맞춰짐
- 절단기 높이 (H) 일때, 떡의 길이가 h이상이면 잘리고, 이하면 안잘림
- ex) 19, 14, 10, 17 일때, h =15이면 → 4,0,0,2로 손님은 6cm를 가져감
- M길이 요청시, 적어도 M만큼의 떡을 얻기위해 절단기에 설정할 수 있는 높이의 최대
idea
- 적절한 높이를 찾을떄까지, 이진 탐색
- 0~n 일때, n이 너무 커서 조건 범위가 크면, 이진 탐색 체크하기 ( n ≥ 10억이상 )
n,m = list(map(int,input().split(' '))) #떡 개수 = n, 길이 = m array = list(map(int,input().split())) #각 떡의 개별 높이 정보 입력 start = 0 end = max(array) #가장 긴 떡 길이 res = 0 while (start <= end): total = 0 mid = (start + end) // 2 for x in array: #x는 현재 떡의 길이 if x > mid: #잘랐을때 떡의 양 계산 total += x - mid if total < m: #떡의 양이 부족하면 더 자르기 end = mid - 1 else : #떡의 양이 충분한 경우 덜 자르기 ( m이상, 떡갖기) res = mid # 최대한 덜 잘렸을떄가 정답 start = mid + 1 print(res)
문제2) 정렬된 배열에서 특정 수의 개수 구하기
수행 과정
- N개 원소를 가진 수열일 오름차순, 이때 x가 등장하는 횟수?
- O(logN) 으로 조건이 정해져 있어서, 알고리즘을 설계하지 않으면 시간초과가 된다( 선형탐색은 안됨)
idea
- 이진탐색 사용
- 특정값이 존재하는 첫번째 위치와 끝 위치를 찾아서 횟수 계산하기
from bisect import bisect_left, bisect_right n,x = map(int,input().split()) array = list(map(int,input().split())) # 배열에서 특정 범위 원소 개수 구하기 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 countNum = count_by_range(array,x,x) if countNum == 0: print(-1) else; print(countNum)
이진탐색 - 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 탐색
- 시작, 끝, 중간점이 있음
- 중간점은 소수점 이하 제거한 값 ( 중간이 명확히 안나눠지는경우 )
- 리스트가 정렬이 되어 있어야만하다
- O(logN)
- 순차 탐색은 데이터를 앞에서부터 탐색함 ( 이진과는 다름 )
#재귀 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) #반복문 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())) res = binary_search(array,target,0,n-1) if res == None: print("원소 존재하지 않음") else: print(res + 1) #인덱스 값이므로 res + 1을 해줘야 한다
파이썬 이진 탐색 라이브러리
파라메트릭 서치
- 이진 탐색 사용
- 최적화 문제 → 결정문제 형태를 바꾸어 해결 ( 결정문제는 예 or 아니오 로 바꿔 해결하는 방법 )
- 특정 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제
- 탐색 범위가 너무 크면 이진탐색을 생각해야 한다.
문제1) 떡볶이 떡 만들기
수행과정
- 떡볶이의 길이는 절단기로 일정하게 맞춰짐
- 절단기 높이 (H) 일때, 떡의 길이가 h이상이면 잘리고, 이하면 안잘림
- ex) 19, 14, 10, 17 일때, h =15이면 → 4,0,0,2로 손님은 6cm를 가져감
- M길이 요청시, 적어도 M만큼의 떡을 얻기위해 절단기에 설정할 수 있는 높이의 최대
idea
- 적절한 높이를 찾을떄까지, 이진 탐색
- 0~n 일때, n이 너무 커서 조건 범위가 크면, 이진 탐색 체크하기 ( n ≥ 10억이상 )
n,m = list(map(int,input().split(' '))) #떡 개수 = n, 길이 = m array = list(map(int,input().split())) #각 떡의 개별 높이 정보 입력 start = 0 end = max(array) #가장 긴 떡 길이 res = 0 while (start <= end): total = 0 mid = (start + end) // 2 for x in array: #x는 현재 떡의 길이 if x > mid: #잘랐을때 떡의 양 계산 total += x - mid if total < m: #떡의 양이 부족하면 더 자르기 end = mid - 1 else : #떡의 양이 충분한 경우 덜 자르기 ( m이상, 떡갖기) res = mid # 최대한 덜 잘렸을떄가 정답 start = mid + 1 print(res)
문제2) 정렬된 배열에서 특정 수의 개수 구하기
수행 과정
- N개 원소를 가진 수열일 오름차순, 이때 x가 등장하는 횟수?
- O(logN) 으로 조건이 정해져 있어서, 알고리즘을 설계하지 않으면 시간초과가 된다( 선형탐색은 안됨)
idea
- 이진탐색 사용
- 특정값이 존재하는 첫번째 위치와 끝 위치를 찾아서 횟수 계산하기
from bisect import bisect_left, bisect_right n,x = map(int,input().split()) array = list(map(int,input().split())) # 배열에서 특정 범위 원소 개수 구하기 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 countNum = count_by_range(array,x,x) if countNum == 0: print(-1) else; print(countNum)
'알고리즘' 카테고리의 다른 글
[알고리즘] M 기업 코딩테스트 (0) 2022.09.26 [알고리즘] 최단경로 정리 (1) 2022.09.26 [알고리즘] 정렬 정리 (1) 2022.09.16 [알고리즘] 구현 정리 (0) 2022.09.16 [알고리즘] dfs / bfs 정리 (0) 2022.09.16 - 시작, 끝, 중간점이 있음