이진탐색 문제

데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘이다.

기본 알고리즘

1.배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교
2.X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로,
X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색
3.위의 과정을 해당 값을 찾을 때까지 반복

코드로 표현하면 아래와 같다.

def binary_search(array, target, start, end):
  while start <= end:
    mid = (start + end) //2
    #찾은 경우 중간점 인덱스 반환
    if array[mid] == target:
      return mid
    #중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
    elif array[mid] > target:
      end = mid - 1
    #중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
    else:
      start = mid + 1
  return None

탐색 범위가 반씩 줄어듦으로 시간 복잡도는 O(logN)이다.

문제유형

백준 18870번, 좌표압축

이진탐색 인덱스를 활용한 기본문제. x보다 작은 원소는 몇개인지를 풀기위함이다. mid 인덱스를 반환함으로서 해결한다. 이진탐색 기초코드와 다를 게 거의 없다.

문제 설명

처음에는 문제이해가 잘 가지 않았다... Xi를 좌표 압축한 Xi'가 있다고 하면 이 값이 Xi>Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다고??? 예제 입력과 출력을 보면 이해가 간다.

2 4 -10 4 -9 가 주어지면 index=0인 2는 2보다 작은 원소는 -10,-9이므로 2로 압축된다. index=1인 4는 4보다 작은 원소는 2, -9,-10이므로 3으로 압축된다. index=2인 -10은 -10보다 작은 원소는 없으므로 0으로 압축된다... 이런식으로 2,3,0,3,1이 나오게 된다.

접근

처음에는 for문을 돌리려고 했지만 배열의 길이 N이 1,000,000까지 가기 때문에 O(N2)인 복잡도로 구성할 경우 100만의 제곱...시간초과는 물론 좋지 않다.

for 문을 1번 돌면서 본 원소보다 작은 원소가 몇개인지만 세면 되도록 구성할 수 있도록 하고, 셀 때 이진탐색을 이용하면 시간 복잡도가 O(NlogN)이 나온다.

코드

n = int(input())
data = list(map(int,sys.stdin.readline().split()))
sorted_data = copy.deepcopy(data)
sorted_data = list(set(sorted_data)) #중복원소 제거
sorted_data.sort(reverse=False) #[-10, -9, 2, 4]

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

for i in data:
   result = binary_search(sorted_data, 0, len(sorted_data)-1, i)
   print(result, end=" ")

백준 1654번,랜선자르기

문제설명

주어진 제 각각의 k개의 랜선을 동일한 길이로 잘라서 n개로 만들어야 한다. 근데 그 길이의 최댓값을 구해야 한다.

접근

이 문제는 이진 탐색을 이용해 조건을 만족하는 최댓값/최소값을 구하는 것이 매개변수 탐색이다. 말만 거창하고 그냥 이진탐색이다.
일단 k개의 랜선이 주어지고 같은 길이로 잘라서 n이 나와야 한다면, 랜선을 임의의 길이로 자른다음 개수가 n과 맞는지 확인해야한다.
여기까지는 생각하기 쉬운데 어떻게 길이의 최댓값을 구할 것인지 아이디어를 이진탐색으로 번뜩 떠올려야 한다. 난 안되던데
어떤 조건일 때 이진탐색의 기준인 mid값을 올리고, 내려야 하는지 정해야 한다.
1과 가장 긴 랜선의 길이의 중간값으로 시작해서 그 값으로 랜선을 잘랐을 때 총 개수가....

구하고자하는 n개보다 크다 -> 더 크게 잘라야 한다는 뜻이므로 mid+1
구하고자하는 n개와 같다 -> 길이의 최댓값을 구해야 하므로 더 크게 가보자 mid+1
구하고자하는 n개보다 작다 -> 더 작게 잘라야 한다는 듯이므로 mid-1

코드

import sys
k, n = map(int, sys.stdin.readline().split())
lan = [int(input()) for _ in range(k)]
start, end = 1, max(lan) #이 부분이 매개변수 탐색의 핵심이다


while start <= end:
   mid = (start + end) // 2
   num = 0 #랜선 개수

   for i in lan:
      num += i // mid
   if num >= n:
      start = mid + 1
   else:
      end = mid - 1
print(end)