이분탐색이란? 이분탐색은 정렬되어 있는 배열에서 사용 가능한 탐색 방법으로, 탐색 범위를 매번 반으로 쪼개 나가며 탐색하는 방법을 얘기합니다. 일반적인 탐색 방법과 비교하기 위해 다음과 같은 문제를 예시로 들어봅시다. 1~N 사이의 자연수로 이루어진 길이가 N인 수열이 있습니다. 이 수열에서 1 이상 N 이하의 정수 K는 몇 번째에 위치해 있는지 구하고자 합니다. 이를 완전탐색으로 해결하면 1번째 값부터 N번째 값까지 일일이 확인해보는 O(N)의 방법이 있습니다. 하지만 N이 100,000 이상 혹은 더욱 커지면 비효율적으로 동작하므로 더욱 빠르게 동작하는 알고리즘이 필요합니다. 만약 수열이 오름차순으로 정렬되어 있다면 이분탐색이라는 알고리즘을 적용할 수 있고, 이의 시간복잡도는 O(logN)입니다. 이..

N, K = map(int, input().split()) ele = [] for _ in range(N): ele.append(int(input())) s = 1 e = max(ele) while s

import sys input = sys.stdin.readline N,M = map(int, input().split()) trees = list(map(int, input().split())) s = 1 e = max(trees) while s M: s = mid +1 elif ans == M: e = mid break else: e = mid -1 print(e) 이분 탐색 익숙해질때까지 풀어보자!!

import sys input = sys.stdin.readline n, m = map(int, input().split()) powerList = [] nameList = [] for i in range(n): name, power = input().split() power = int(power) if powerList and powerList[-1] == power: # 가장 처음 칭호만 저장해주기 위해 continue powerList.append(power) nameList.append(name) def binary_search(p): left = 0 right = len(powerList) - 1 while left powerList[mid]: left = mid + 1 else: right =..

import sys input = sys.stdin.readline N = int(input()) cities = list(map(int, input().split())) budgets = int(input()) # 예산 start, end = 0, max(cities) # 시작 점, 끝 점 # 이분 탐색 while start mid: total += mid else: total += i if total M)는 max(budget)을 출력한다. 3) mid를 start와 end의 중간으로 두고, mid와 예산(i) 중 작은 값을 total_budget에 더해준다. 4-1) total_budget이 목표 수준(M)을 초과하면 mid-1을 end로 두고 다시 while문 반복 4-2) total_budget..