백준 이진 탐색 (3) 썸네일형 리스트형 이진 탐색(이분 탐색): 백준 2110 파이썬 문제: https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 풀이: 이 문제는 처음에 이해하기가 다소 어려웠다. 문제에서 집 좌표의 범위가 (0 ≤ x ≤ 1,000,000,000)와 같아서 이진 탐색을 사용해야 하겠다는 생각은 들었지만, 찾아야 하는 수 target을 어떤 것으로 할지 떠오르지 않았다. 구글링을 해서 힌트를 얻어 문제를 풀 수 있었다. 이 문제는 이진 탐색의 방법을 응용해서 해결하.. 이진 탐색(이분 탐색): 백준 1654 파이썬 문제: https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 정답: import sys k, n = map(int, sys.stdin.readline().split()) array = [int(sys.stdin.readline()) for _ in range(k)] # 이진 탐색을 위한 시작점과 끝점 설정 start = 1 end = max(array) # 이진 탐색 수행(반복적) result = 0 while(start 이진 탐색: 백준 1920 파이썬 문제: https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 정답: import sys n = int(sys.stdin.readline()) n_arr = list(map(int, sys.stdin.readline().split())) m = int(sys.stdin.readline()) m_arr = list(map(int, sys.stdin.readline().split())) def binary_.. 이전 1 다음
