함께 한 문제
이분 탐색: BOJ 1920 수 찾기
매개변수 탐색 : BOJ 2110 공유기 설치

이분 탐색

이분 탐색은
정렬된 배열에서 원하는 값의 위치를 찾기 위해
배열을 반으로 나누어 탐색하는 알고리즘이다.

탐색 대상 배열이 정렬된 상태(일반적으로 오름차순 정렬)임을 전제하기 때문에,
탐색 대상인 배열 target 내 임의의 index i에서
찾고자 하는 값 key와 target[i]의 대소 비교를 통해
key 가 존재할 수 있는 범위의 경계를 구분지을 수 있다.

이분 탐색은 정렬된 배열의 위와 같은 성질을 이용해서 진행된다.

1. 경계의 시작과 끝 지정

   탐색 대상이 배열이기 때문에
   경계의 시작지점은 0, 끝지점은 전체길이-1 인 마지막 인덱스로 시작한다.

# 범위의 시작과 끝
start = 0
end = len(target)-1

2. 탐색

   탐색 대상을 절반으로 나누며 탐색을 진행한다.
   start와 end 의 중간 위치를 계산하여
   찾고자 하는 값(key)과의 대소 비교를 통해 다음 탐색 범위를 지정한다.

  # 범위의 시작과 끝
  start = 0
  end = len(target)-1
  
  # 반복문을 돌며 탐색
  while True:
  	# 중간 위치
  	mid = (start + end) // 2
    
    # key와 같다면, 탐색 종료    
    if target[mid] == key:
    	break
    # key보다 크다면, 탐색 범위를 (start ~ mid-1)로 설정
    elif target[mid] > key:
    	end = mid - 1
    # key보다 작다면, 탐색 범위를 (mid+1 ~ end)로 설정
    else: # target[mid] < key
    	start = mid + 1

문제

문제 : BOJ 1920 수 찾기

탐색 대상(정렬된 리스트)이 A, 탐색할 숫자들이 있는 리스트가 B이다.

binary_search()의 target으로 넘겨주는 리스트는 항상 A이고
key로 넘겨주는 숫자는 B를 순회하며 B가 가지고 있는 요소를 하나씩 꺼내어 전달한다.

문제에서는 '값이 존재하는지'를 확인하고자 했기 때문에,
탐색하는 반복문이 종료되면
마지막으로 탐색한 값(target[e])이 key와 같은지 확인하여
그 여부를 return 해준다.

구현

두 가지 방법으로 구현해보았다.

[ 코드 1 ] : Lower Bound
Lower Bound는 찾는 값보다 크거나 같은 값이 최초로 나타나는 위치를 탐색하는 방법이다.

n = int(input())
# 이분 탐색을 위해, 탐색할 리스트는 정렬되어있어야 한다.
A = sorted(list(map(int, input().split())))

m = int(input())
B = list(map(int, input().split()))

def binary_search(key, start, end, target):
    s = start
    e = end
    while s < e:
        m = (s + e) // 2
        if target[m] >= key:
            e = m
        else:
            s = m + 1
    print(int(target[e]==key))


for b in B:
    binary_search(b, 0, n-1, A)

[ 코드 2]

아래 코드는 탐색 하려는 값보다 작거나 같은 값의 위치를 알 수 있다.

n = int(input())
# 이분 탐색을 위해, 탐색할 리스트는 정렬되어있어야 한다.
A = sorted(list(map(int, input().split())))

m = int(input())
B = list(map(int, input().split()))

def binary_search(key, start, end, target):
    s = start
    e = end
    while s < e:
        m = (s + e) // 2 + 1
        if target[m] > key:
            e = m - 1
        else:
            s = m
    print(int(target[e]==key))


for b in B:
    binary_search(b, 0, n-1, A)

이 코드의 경우에는
target[m]이 key 보다 같거나 작을 경우 시작 지점을 중간 지점까지 좁혀주는데,
m은 항상 2로 나눈 몫이기 때문에
s = n, e = n+1 일 때 m = n이 되어 간격이 끝까지 좁혀지지 않게된다..
따라서 중간 지점의 위치를 구할 때 +1 을 해주는 방식으로 구현하였다.

---

매개변수 탐색

이분 탐색을 이용하여 주어진 조건을 만족하는 최소/최대값을 찾는 탐색 방법

이분 탐색의 경우 시작s과 끝e index를 이용해 중간값m을 기준으로
문제를 절반으로 나누며 탐색한다.

이때, 왼쪽 절반과 오른쪽 절반 중 어떤것을 선택할 것인지를
이분탐색에서는 key값과 탐색 대상 리스트의 m번 index 요소와의 대소 비교를 통해 판단했는데,

매개변수 탐색에서는
주어진 조건을 판단하는 함수를 이용해서 결정 가능한 값을 return 하고
이를 key와 비교해서 판단한다.

문제와 함께 알아보자

문제 : BOJ 2110 공유기 설치

무엇을 탐색할 것인지

문제에서 알 수 있는건
서로 좌표가 같은 집은 존재하지 않기 때문에 인접한 두 집 사이 거리의 최소값은 1이라는 것,
그리고 입력에서 설치 해야할 공유기의 갯수를 정해준다는 것이다.

맨 처음 들었던 생각은 공유기의 수로 이분 탐색을 진행하자는 것이었는데,
조금만 더 생각해보니 공유기 갯수의 최소값과 최대값이 무엇인지 알 수 없고,
또한 이분 탐색을 진행한 결과가 입력받은 C가 되도록 해야하는데
그러기 위해서는 우리가 최종적으로 구해야 할
가장 인접한 두 집 사이의 거리를 그 전에 알아야 했다.

그러면 반대로, 가장 인접한 두 집 사이의 거리를 이용해서 탐색을 진행하면 어떨까.

가장 인접한 두 집 사이의 거리의 값을 미리 정해두고,
그 조건에 따라서 설치할 수 있는 공유기의 최대 갯수를 구하는 것이다.

0번 집부터 설치한다면, 1번집의 공유기 설치 여부를
미리 정해준 가장 인접한 두 집 사이의 거리 로 판단할 수 있게되고,

거리 최소값의 감소와 증가에 따라
각각 공유기를 더 많은 집에 설치하거나, 더 적은 집에 설치할 수 있다.

구현

먼저, 두 집의 좌표차가 곧 두 집의 거리이므로
공유기를 마지막으로 설치한 집에서 순차적으로 거리를 판단하기 위해서는
집의 좌표를 담은 리스트는 정렬된 상태여야 한다.

import sys

n, c = map(int, sys.stdin.readline().split())
house = sorted([int(sys.stdin.readline().rstrip()) for _ in range(n)])

그 다음, 최소 거리가 주어지면 설치 가능한 집의 개수를 돌려주는 함수를 작성한다.

1. 공유기를 마지막으로 설치한 위치와 현재 위치 사이의 거리가 최소 거리보다 작다면,
   공유기를 설치하지 않고 다음 집으로 이동한다.

2. 만약 두 집 사이의 거리가 최소 거리 보다 크거나 같다면,
   공유기를 설치하고 마지막으로 설치한 위치 를 현재 위치 로 갱신해주며
   설치 횟수를 1 증가시켜준다.
   
   

[ 최소 거리로 집 개수 구하기 ]

# (정렬된 집 좌표, 최소거리)를 파라미터로 전달받아 
# 설치 가능한 공유기 최대 갯수를 return
def count(target, min_dist):
    pre = 0     # 직전에 설치한 집의 index. 0번째 집에 설치하고 시작
    count = 1   # 설치 횟수를 계산. 0번째 집에 설치했기 때문에 횟수는 1부터 시작
    for i in range(1, len(target)):
        # 두 집 사이의 거리가 최소 거리보다 작으면 설치 불가
        if target[i]-target[pre] < min_dist:
            continue
        # 그렇지 않으면 설치
        else:
            pre = i     # i에 설치했으므로, 다음 탐색부터는 '직전에 설치한 집의 index'가 i가 됨
            count += 1  # 설치 횟수 1 증가
    return count

이제 위의 함수를 이용해서 이분 탐색을 진행한다.
key 값은 설치해야 할 공유기의 갯수이며,
def count()에서 리턴된 값과의 비교를 통해 탐색 범위를 좁혀준다.

이 때, 이분 탐색은 lower bound로 진행되어야 한다.

lower bound를 사용해야하는 이유

C = 4일때,
설치 가능한 최소거리에 대한, 설치 가능한 공유기의 최대 갯수가 다음과 같다고 하자.

최소거리	최대 설치가능갯수
...	...
4	5개
5	3개
...	...

주어진 '설치 할 공유기의 갯수'가 4개 이므로
그것보다 적은 수인 3개의 공유기만을 설치할 수는 없다.
( 3개를 설치했을 때의 최소 거리를 가질 수 없다. )

따라서, 공유기 4개(= C)를 설치할 때 가질 수 있는 최소 거리는
최대 5개의 공유기를 설치 할 수 있는 최소 거리와 같다.

lower bound는 찾고 싶은 값 key를 탐색한 결과로
"key 보다 크거나 같은 값이 최초로 나타나는 위치" 를 찾을 수 있기 때문에
위와 같은 경우에서 최대 5개를 설치할 수 있는 최소거리를 알 수 있다.

[ 전체 코드 ]

import sys

n, c = map(int, sys.stdin.readline().split())
house = sorted([int(sys.stdin.readline().rstrip()) for _ in range(n)])

def solution(target, key):
    s = 1
    e = target[len(target)-1] - target[0]
    while s < e:
        m = (s+e) // 2 + 1
        # m을 최소 거리로 할 때, 
        # '설치 가능한 공유기의 최대 갯수' < '설치 하려는 공유기의 갯수' 이면
        # 최소 거리를 더 늘려도 됨 
        # (최소 거리가 증가하면 전체 간격이 늘어나서 설치 가능한 공유기 갯수가 감소하므로)
        if count(target, m) < key:
            e = m - 1
        # 그렇지 않다면, 반대로 최소 거리를 줄여야 함
        else:
            s = m + 1
    return e

# (정렬된 집 좌표, 최소거리)를 파라미터로 전달받아 
# 설치 가능한 공유기 최대 갯수를 return
def count(target, min_dist):
    pre = 0     # 직전에 설치한 집의 index. 0번째 집에 설치하고 시작
    count = 1   # 설치 횟수를 계산. 0번째 집에 설치했기 때문에 횟수는 1부터 시작
    for i in range(1, len(target)):
        # 두 집 사이의 거리가 최소 거리보다 작으면 설치 불가
        if target[i]-target[pre] < min_dist:
            continue
        # 그렇지 않으면 설치
        else:
            pre = i     # i에 설치했으므로, 다음 탐색부터는 '직전에 설치한 집의 index'가 i가 됨
            count += 1  # 설치 횟수 1 증가
    return count

sys.stdout.write(f'{solution(house, c)}')