⭐ 성찰

절대 코딩 테스트에서 while문을 쳐다 보지 말라 - 무한루프에 빠져버린 15일의 본인

모든 while문은 for문으로 대체 가능하다.

이진 탐색 문제는 🌟 (1) 이진 탐색 대상 정하기 (2) 이진 탐색 로직 수립하기🌟 의 흐름으로 진행해야한다. (1) 이진 탐색 알고리즘의 탐색 대상 = 구해야 하는 값 (2) lower bound 문제인지 uppper bound 문제인지 확인하기 위해서 항상 직접 손으로 그린 후, 이진 탐색 로직을 짜라.

⭐ 이진 탐색 시 사전 정렬을 까먹지 말기!!!!!

이진 탐색의 e를 정할 때, e를 계산하는 오버헤드가 크면 e를 줄이지 않고 고정값을 사용하자.

📖 좋은 코드

# 배열 내의 모든 원소 중 d이상의 거리를 만족하는 최초 원소를 찾으며 개수 파악
def install(d):
  curr = houses[0]
  cnt = 1 # 맨 처음 값은 따로 처리해줌
  for i in range(1, len(houses)):  # 따로 처리해준 값은 범위에서 빼고 수행
    if houses[i] >= curr + d:
      curr = houses[i]
      cnt += 1
  return cnt >= c

❓ 문제 상황

공유기 설치

👨‍💻 문제 해결: 이진 탐색

✅ 1차 풀이: 공유기 설치 가능 여부를 기반으로 이진 탐색

⌛ 시간복잡도: O(nlogm) <= 600만

n = install 함수의 시간복잡도 = n의 최대길이 = 200,000
m = 최대 높이 = 10,000,000
👨‍💻 구현

이진 탐색 문제는 (1) 이진 탐색 대상 정하기 (2) 이진 탐색 로직 수립하기의 흐름으로 진행해야한다. (1) 구해야 하는 대상 = 가장 인접한 두 공유기 사이 거리의 최대값이므로 0 <= d <= 10억 사이에서 이진탐색 수행 (2) 최소 거리를 m으로 공유기를 설치할 때 총 c개 이상 설치 가능한지 확인하여, 설치 가능하다면 임시 저장해 최종값 반환
이 때, e = 10억이 아니라 줄여줄 수도 있지만, 어차피 logN안의 N값이므로 유의미한 차이가 없을 수도 있어, 연산 오버헤드와의 trade-off를 생각한 뒤 결정하자.
```
import sys
```

input = sys.stdin.readline

n, c = map(int, input().split()) houses = [int(input()) for _ in range(n)]

houses.sort()

def install(d): curr = houses[0] cnt = 1 # 맨 처음 값은 따로 처리해줌 for i in range(1, len(houses)): # 따로 처리해준 값은 범위에서 빼고 수행 if houses[i] >= curr + d: curr = houses[i] cnt += 1 return cnt >= c

s = 0 e = 1000000000

e = houses[-1] - houses[0] # 가능한 최대거리

result = 0

while s <= e: m = (s+e) // 2 if install(m): result = m s = m + 1 else: e = m - 1

print(result)

ericagong / algorithm_solving

[이진탐색] 공유기 설치 #24