[Python] 이진 탐색 기초/ 백준 2110번 공유기 설치 파이썬 풀이

 

이진탐색: 배열 내부의 데이터가 정렬되어 있을 때
시작점, 끝점, 중간점을 이용하여 원하는 값을 찾는 탐색법

 

시작점을 start 중간점을 mid, 끝점을 end라고 부르겠다

이진탐색은 주어진 범위가 엄청 클 때 사용할 수 있고, 배열의 원소들은 오름차순으로 정리되어야 한다.

 

코드 작성 순서

(1) 이진탐색의 시작점과 끝점을 설정

start= 0

end = 배열에서 가장 큰 수, 혹은 주어진 최대값

(2) 이진탐색 수행

while(start <= end) 

mid =  (start + end) // 2

mid가  찾는 값보다 클 경우,
end = mid-1
mid가 찾는 값보다 작을 경우,
start = mid +1
이를 반복하여 mid == target일 경우 return한다

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

이런 식으로 범위 매우 클 때 주로 사용된다. 

 

예제문제

첫번째 줄에는 원소의 개수 n과 찾고자하는 수 target을 입력받는다 두번째 줄에는 n개의 원소를 가진 배열 arr을 공백으로 구분되어 입력받는다. 세번째 줄에는 몇번째에 위치했는지 출력한다.

(arr[0]에 위치할 경우 출력값은 1이다)

예제 입력 1

10 7
1 3 5 7 9 11 13 15 17 19

예제 출력 1

4

 

예제 입력 2

10 7
1 3 5 6 9 11 13 15 17 19

예제 출력 2

원소를 찾을 수 없습니다

 

 

import sys
input = sys.stdin.readline

def binary_search(arr, target, start, end):
    while start <= end:
        mid = (start + end) // 2  # 중간점은 (시작점+끝점) // 2
        if arr[mid] == target:  # 타겟을 찾은 경우, return
            return mid
        elif arr[mid] <= target:  # 중간점이 타겟이하인 경우 오른쪽 확인 (더 큰 영역)
            start = mid + 1
        else:  # 중간점이 타겟보다 큰 경우 왼쪽 확인 (더 작은 영역)
            end = mid - 1
    return None

n, target = list(map(int, input().split()))  # 원소의 갯수, 찾고자하는  문자열 입력
arr = list(map(int, input().split()))  # 전체 문자열 입력
result = binary_search(arr, target, 0, n-1)  # 함수 실행

if result == None:
    print("원소를 찾을 수 없습니다")
else:
    print(result)

 

 

 

 

공유기 설치
백준 2110번 골드 4

 

 

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

예제 입력 1 

5 3
1
2
8
4
9

예제 출력 1 

3

힌트

공유기를 1, 4, 8 또는 1, 4, 9에 설치하면 가장 인접한 두 공유기 사이의 거리는 3이고, 이 거리보다 크게 공유기를 3개 설치할 수 없다.

 

 

 

아이디어 생각하기

 

문제요약 : 공유기 N개를 설치하면 집 사이의 거리가 최대인 곳은 몇일까

mid는 집들 사이의 중간값이 아니다.....

{최소 거리 (1) + 최대 거리(가장 끝에 있는 집 - 가장 처음있는 집) } // 2

예제에서의 mid = (1+ 9 - 1) // 2 = 8이다

공유기를 설치할 수 있는 곳은 마지막으로 설치한 곳과 설치예정 장소의 거리가 mid 보다 커야한다

즉, 예제에서는 집 사이의 거리가 4 이상이면 설치 가능하다.

우선 시작점에는 무조건 설치한다.

예제에 나온 1,2,4,8,9 을 예시로 들면

1에 설치를 무조건 설치

그 다음 1<=> 2와는 거리가 1이므로 설치 x

1<=>4  거리가 3이므로 설치 x

1<=>8 거리가 7이므로 설치 o

8<=> 9 거리가 1이므로 설치 x

하지만, 이렇게 되면 1, 4  두군데에만 설치하게 되어 C=3에 어긋난다.

따라서 이럴 떈,  end = mid -1를 주어 공유기 사이의 간격을 좁히고, 다시 탐색을 하자.

 

"""
문제요약 : 공유기 N개를 설치하면 집 사이의 거리가 최대인 곳은 몇일까

(1) 공유기 설치 위치
중간값보다 커야 설치가 가능하다.
처음 거리보다 다음 설치한 공유기의 거리가 더 넓게 거리를 잡아간다
(마지막 설치 집 -설치예정 집) > mid
다 설치를 했는데 C보다 작으면 공유기 간격을 좁힌다
공유기 개수가 C보다 크면 공유기 간격을 넓힌다.
"""
import sys
input = sys.stdin.readline
N, C = map(int, input().split())
home = []

for _ in range(N):
    home.append(int(input()))

home.sort()

start, end = 1, (home[-1]-home[0])  # 시작점, 끝점
answer = 0

while start <= end:
    mid = (start + end) // 2
    sum = 1
    cur = home[0] #현재 집의 위치 

    #두번째 집부터 탐색
    for i in range(N):
        if home[i] - cur >= mid:    #설치예정인 집이 마지막으로 설치한 곳과의 거리보다 크면 설치
            sum += 1
            cur = home[i] #마지막 설치위치 기록
    #만약 총 설치값이 C보다 크면 
    if sum >= C:
        answer = mid #일단 기록 
        start = mid + 1 #간격을 줄인다
    else: #총 설치값이 C보다 작으면
        end = mid - 1 #간격을 늘린다

print(answer)