이것이 코딩 테스트다 PART3 with python : 이진탐색

이것이 코딩 테스트다 PART3 with python : 이진탐색

28. 고정점 찾기(난이도 1.5)

# 찾고자하는 값 = mid

n = int(input())
array = list(map(int,input().split()))

def binary_search(array, start, end):
  while start <= end:
    mid = (start + end) // 2
    if array[mid] == mid:
      return mid
    elif array[mid] > mid:
      end = mid - 1
    else:
      start = mid + 1
  return None

result = binary_search(array, 0, n-1)
print(result)

29. 공유기 설치

가장 인접한 두 공유기 사이의 거리의 최댓값 탐색

이진 탐색으로 '가장 인접한 두 공유기 사이의 거리'를 조절해가며, 매 순간 실제로 공유기를 설치하여 C보다 많은 개수로 고유기를 설치할 수 있는 지 체크하여 문제를 해결한다.

n, c = list(map(int, input().split()))

array=[]
for _ in range(n):
  array.append(int(input()))
array.sort()

# 가능한 최소 거리
start = 1
# 가능한 최대 거리
end = array[-1] - array[0]

result = 0

while (start <= end):
  # mid: 가장 인접한 두 공유기 사이의 거리 
  mid = (start+end)//2
  value = array[0]
  count = 1

  #현재의 mid값을 이용해 공유기를 설치 
  for i in range(1,n):
  	# 공유기 설치
    if array[i] >= value + mid:
      value = array[i]
      count += 1
  # 공유기의 개수가 c보다 같거나 크면 갭의 크기를 늘린다.
  if count >= c:
    start = mid + 1
    result = mid
 # 공유기의 개수가 c보다 작으면 갭의 크기를 줄인다.
  else:
    end = mid -1

print(result)