[BOJ] 2110 : 공유기 설치 [이분 탐색](Python)

문제 링크

https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

소스 코드

import sys

def main():
    N,C = map(int, input().split())

    house = []
    for _ in range(N):
        house.append(int(sys.stdin.readline().strip()))
    house.sort()
    
    answer = 0
    left, right = 1, house[-1]-house[0]
    while left <= right: # 간격의 최소/최대가 곧 탐색 범위
        gap = (left+right) // 2 # 간격
        cur = house[0] # 공유기 설치 위치
        cnt = 1 # 공유기 설치 대수

        for i in range(1,N):
            if house[i] >= cur + gap:
                cur = house[i] # 공유기 위치 갱신
                cnt += 1 # 공유기 설치 대수 증가
        
        if cnt >= C: # 공유기 충분 -> 간격 늘리기
            left = gap + 1
            answer = gap
        else: # 공유기 부족 -> 간격 줄이기
            right = gap - 1
    
    print(answer)

if __name__ == '__main__':
    main()

 

해설

• 이분 탐색, binary search

작년에도 풀어내지 못했는데 이번에도 자력으로는 버거웠습니다 하하..

얼핏보면 DP랑 합쳐진 유형처럼 느껴지기도 하고..

다시 풀어봐도 뭘 binary search 해야 할지 참 고민이 됩니다 😅

---

ChatGPT(3.5)의 풀이 🤖

나보다 해설이 깔끔한데..? 👍🏻

---

시간복잡도

네.. GPT가 알려준대로(범위를 알려주지 않은 걸 감안하면 정답) 이 이분 탐색 알고리즘은 O(NlogX)의 시간 복잡도를 지닙니다.

이분 탐색은 O(logX)입니다.

왜냐하면 범위가 X인 대상으로 이분 탐색을 수행하는 경우, 이 X을 반복적으로 2로 나누기 때문에 최대 log_2(X)번만큼 계산하기 때문입니다.

따라서 while문의 조건 left <= right 자체가 O(logX)번 반복될 것임을 의미하죠.

 

그리고 while문 내의 for문을 통해 길이 N짜리 house 리스트에 대한 탐색이 수행됩니다.

길이 N에 선형적으로 비례하여 연산 횟수가 증가하게 되므로 O(N)입니다.

 

결과적으로 logN 번의 while문이 돌아가는 동안, 매번 N번의 연산이 수행되므로 O(NlogX)이 됩니다.

(상수 시간이 소요되는 연산들은 제외합니다)

---

이분 탐색

그렇다면 뭘 이분 탐색하는지 자세히 뜯어 봅시다!

 

우선 탐색 대상은 문제에서 요구하는 '가장 인접하는 두 공유기 간의 최소 거리'입니다.

다시 말하자면 공유기가 설치된 집 사이의 간격 중 어떤 값이 정답이 된다는 뜻입니다.

두 집 사이 간격의 최솟값은 1일테고 최댓값은 가장 멀리 떨어진 두 집 사이의 거리가 됩니다.

그렇기 때문에 범위의 중간값으로 탐색을 반복하는 것이죠(gap)

left, right = 1, house[-1]-house[0]
while left <= right: # 간격의 최소/최대가 곧 탐색 범위
    gap = (left+right) // 2 # 간격

 

다음은 for문으로 탐색을 진행하며 공유기를 설치하는 과정입니다.

여기서는 while문에서 구한 gap을 기준으로, 현재 공유기가 설치된 위치 + gap 보다 더 멀리 있는 지역을 체크해줍니다.

 

문제의 예시를 떠올려보면 [1, 2, 4, 8, 9] 에서 처음엔 gap = (1 + 8) // 2 = 4입니다.

(1+8인 이유는 최소/최대 거리라서 입니다. 1+9가 아닙니다!!!)

따라서 현재 설치된 위치 2 < 1 + 4 이므로 패스, 4 < 1 + 4 이므로 패스, 8 > 1 + 4이므로 스탑입니다.

정리하면, 탐색하는 공유기 간 거리보다는 더 멀리 떨어진 지역에 공유기를 설치할 수 있다는 것입니다.

for i in range(1,N):
    if house[i] >= cur + gap:
        cur = house[i] # 공유기 위치 갱신
        cnt += 1 # 공유기 설치 대수 증가

 

그럼 이 논리에 따라 공유기를 다 설치하고 나면, 설치된 공유기의 개수를 세어줍니다.

설치된 것이 우리가 가진 제한(C)보다 많다면, 우리는 공유기의 개수를 줄여야 합니다.

즉, 탐색 범위를 늘려서 공유기 간 간격을 더 크게 만들어야 한다는 것이죠.(시작 범위를 옮김)

반대로 설치된 것이 제한보다 적은 경우, 공유기의 개수를 늘려야 합니다.

이때는 탐색 범위를 좁혀서 공유기 간 간격을 작게 만들어야 하죠. (종료 범위를 옮김)

이것이 이분 탐색의 방식입니다.

if cnt >= C: # 공유기 충분 -> 간격 늘리기
    left = gap + 1
    answer = gap
else: # 공유기 부족 -> 간격 줄이기
    right = gap - 1

---

아니 근데 왜 무조건 첫 집부터 시작하는데?

저는 조금 둔해서 그런지 왜 첫 집에 반드시 공유기를 설치하고 가는지 이해가 안 됐습니다.

왜냐하면 조합을 구하다보면 더 효율이 좋은 케이스가 존재할 수 있지 않나? 그렇지 않다라는 것을 어떻게 증명할 수 있나?

라는 생각에 갇혔기 때문이죠 💩

 

하지만 단순하게 생각하면 너무 쉬운 문제였습니다.

만약 문제 예시처럼 5개의 숫자가 정렬되어 있을 때, 두 개의 집에 공유기를 설치하고 그 간격을 가장 크게 한다면 어떤 경우일까요?

두말할 필요 없이 첫 번째와 마지막 숫자의 조합일 것입니다.

 

그렇다면 세 개의 집에 공유기를 설치할 때는 어떨까요?

이때는 첫 번째와 마지막 집을 고정해두고 '최적의 경우'를 찾아야 할 것입니다.

마찬가지로 네 개, 다섯 개.. 등등 숫자를 늘려나간다고 하더라도 간격을 최대한 넓히기 위해서는 첫 집과 마지막 집은 고정적으로 공유기가 설치되어야 합니다.

 

그러나 우리가 마지막 집도 설치하는 세팅을 하지 않는 이유는 굳이 그럴 필요가 없기 때문입니다.

어차피 left <= right라는 조건 덕분에 left = right가 되는 순간까지 반복문이 돌아가게 되어 있고, 굳이 마지막집을 고정해두지 않더라도 그 전에 최적의 정답이 나올 수도 있기 때문이죠.

따라서 첫 집에 공유기를 설치하고 시작하면 최적의 조합이 보장된다고 볼 수 있습니다.

(우리는 left to right 방식으로 for문을 돌리니까요)

 

여튼 유형 자체의 난이도가 높은 이분 탐색 문제를 풀고 정리해보았습니다.

이분 탐색을 풀기 위해서 '어떤 것을 탐색할 것인가', '범위는 어떻게 정할 것인가'를 명확히 정하는 습관을 들여야겠습니다!