본문 바로가기

코딩 테스트/이진 탐색8

기사 검색 p. 370 from bisect import bisect_left, bisect_right def count_by_value(array, left_q, right_q): left=bisect_left(array, left_q) right=bisect_right(array, right_q) return right-left def solution(words, queries): answer = [] # 단어들의 길이 별로 배열 만들기 array=[[] for _ in range(10001)] reverse_array=[[] for _ in range(10001)] # 단어의 길이에 맞게 배열에 저장 for word in words: array[len(word)].append(word) reverse_arra.. 2021. 2. 20.
공유기 설치 p. 369 n, c = map(int, input().split()) house=[] for i in range(n): house.append(int(input())) house.sort() start = house[1]-house[0] end = house[-1]-house[0] result = 0 while start 거리를 조절해가며 최대의 거리를 찾아야 해 거리를 이진탐색으로 조절해보자 --> 단순 탐색을 할 경우 시간 초과 ( 집의 개수 최대 200,000 ) -> O(N^2) 2021. 2. 20.
고정점 찾기 p. 368 def b_s(array, start, end): if start>end: return None mid=(start+end)//2 if mid==array[mid]: return mid elif array[mid]>mid: return b_s(array, start, mid-1) else: return b_s(array, mid+1, end) n= int(input()) array=list(map(int, input().split())) result=b_s(array, 0, n-1) if result==None: print(-1) else: print(result) 주의 return 잘 사용하기.. 2021. 2. 18.
정렬된 배열에서 특정 수의 개수 구하기 p. 367 방법1. 특정 수의 개수 다 세기 cnt=0 def b_s(array, target, start, end): global cnt if start>end: return cnt middle=(start+end)//2 if array[middle]==target: cnt+=1 b_s(array, target, middle+1, end) b_s(array, target, start, middle-1) elif array[middle] < target: b_s(array, target, middle+1, end) else: b_s(array, target, start, middle-1) n,x = map(int, input().split()) array=list(map(int, input().spli.. 2021. 2. 18.
떡볶이 떡 만들기 p. 201 n,m = map(int, input().split()) array=list(map(int, input().split())) start=0 end=max(array) result = 0 while start middle: length += (i-middle) if length < m: end=middle-1 else: start=middle+1 result=middle print(result) 파라메트릭 서치 유형 2021. 2. 18.
부품 찾기 p. 197 방법 1. 이진 탐색 def binary_search(array, target, start, end): if start>end: return None middle=(start+end)//2 if array[middle]==target: return middle elif array[middle] 2021. 2. 18.

티스토리툴바