이진탐색

2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net binary search 카테고리에 들어있는 문제인데 대체 무엇을 이진 탐색해야 하는지 파악하는데 꽤 오랜 시간이 걸렸다. 문제를 읽어보면 '가장 인접한 두 공유기 사이의 거리를 최대로 하는'이라는 문구를 볼 수 있다. 여기서 두 공유기 사이의 거리에 대해 이진 탐색을 수행 해야함을 알 수 있다. 코드 import sys input = sys.stdin.readline n, c = map(int, input()..

이진 탐색 데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾음 시간 복잡도 $O(logN)$ 💡 이진 탐색 과정 ① 현재 데이터셋의 중앙값(mid)을 선택 ② 중앙값 > 타깃 데이터(mid>target)일 때 중앙값 기준으로 왼쪽 데이터셋을 선택(end=mid-1) ③ 중앙값 target: # target이 중간점보다 작으면 왼쪽부분 탐색 return binary_se..

2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 코드 n, m = map(int, input().split()) tree = list(map(int, input().split())) # 이진 탐색을 위한 시작점, 끝점 start = 0 end = max(tree) result = 0 # 최종 절단기 높이 while(start mid: # 절단기보다 주어진 나무가 길면 자른 나머지를 total에 추가 total += i - mid # 이진 탐색 if total < m: #..

1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 코드 # 이진 탐색 함수(재귀적 구현) def binary_search(array, target, start, end): if start > end: return None mid = (start + end) // 2 # 중간점 if array[mid] == target: # target을 찾았으면 리턴 return mid elif array[mid] > target: # target이 중간점보다 작으면 왼쪽부분 탐..

bisect은 정렬된 리스트에서 특정 원소를 찾을 때 효과적으로 사용할 수 있는 라이브러리이다. 많은 메소드들 중 bisect_left, bisect_right를 사용하면 많은 문제들을 해결할 수 있다. bisect_left(a, x): 배열 a의 정렬된 상태를 유지하면서 원소 x를 삽입할 수 있는 가장 왼쪽 인덱스를 리턴 bisect_right(a, x): 배열 a의 정렬된 상태를 유지하면서 원소 x를 삽입할 수 있는 가장 오른쪽 인덱스를 리턴 from bisect import bisect_left, bisect_right 정렬된 배열 array=[1, 2, 3, 4, 4, 6, 8, 9]가 있을 때, 4를 삽입할 수 있는 가장 왼쪽 인덱스와 가장 오른쪽 인덱스를 찾기 위해서는 다음과 같이 코드를 작성..