[이진 탐색] 파라메트릭 서치(Parametric Search)

파라메트릭 서치(Parametric Search)

---

파라메트릭 서치(Parametric Search)

 

파라메트릭 서치(Parametric Search)는 최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다. 결정 문제란, '예' 혹은 '아니오'로 답하는 문제를 말한다. '주어진 범위에서 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제'에 주로 파라메트릭 서치를 사용한다.  예를 들어 범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제라면 이진 탐색으로 결정 문제를 해결하면서 범위를 좁혀 나갈 수 있다. 

 

 

* 이진 탐색 개념 참고

[알고리즘] 이진 탐색(Binary Search, 이분 탐색)

 

 

---

문1. 떡볶이 떡 만들기

 

[문제 요약]
절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H 보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다.

예를 들어, 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기 높이를 15cm 로 지정하면 자른 뒤의 떡의 높이는
15, 14, 10, 15cm가 될 것이다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm이다. 손님은 6cm 만큼의 길이를 가져간다.

(출처) 이것이 코딩테스트다 with 파이썬

[입력 조건]
1) 첫째 줄에 떡의 개수 N과 요청한 떡의 길이 M이 주어진다. (1 <= N <= 1,000,000, 1 <= M <= 2.000,000,000)
2) 둘째 줄에는 떡의 개별 높이가 주어진다. 떡 높이의 총 합은 항상 M 이상이므로, 손님은 필요한 양만큼 떡을 사갈 수 있다. 높이는 10억 보다 적거나 같은 양의 정수 또는 0이다.

[출력 조건]
적어도 M 만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

[입력 예시]
4 6
19 15 10 17

[출력 예시]
15

 

풀이 1. 

# 2. 떡볶이 떡 만들기 

n, m = map(int, input().split())
arr = list(map(int, input().split()))

check_range = [i for i in range(1, max(arr))]
check_range.sort(reverse = True)

for i in range(len(check_range)):
  check = check_range[i]
  tteok = []
  for j in range(len(arr)):
    if arr[j] > check:
      tteok.append(arr[j]-check)

  if sum(tteok) >= m:
    print(check)
    break

입력 수가 많이 크지 않은 경우에는 위와 같은 풀이로 답을 찾아도 아무런 문제가 없다. 하지만 입력 수의 범위가 십 억대 이므로 이진 탐색 알고리즘을 생각하는 것이 보편적이다.  이진 탐색 알고리즘의 시간 복잡도는 O(logN)이다. 

 

풀이 2. (이진 탐색)

# 떡볶이 떡 만들기
# 이진 탐색으로 문제 풀기


def binary_search(order, target, start, end):
  result = 0
  
  # 이진 탐색 수행(반복적)
  while start <= end:
    total = 0
    middle = (start + end)//2
	
    for x in order:
      # 잘랐을 때의 떡의 양 계산
      if x > middle:
        total += (x-middle)
	# 떡의 양이 부족한 경우 더 많이 자르기(왼쪽 부분 탐색)
    if total < target:
      end = middle-1
     # 떡의 양이 충분한 경우 덜 자르기(오른쪽 부분 탐색)
    else:
      result = middle
      start = middle + 1
  return result

n, m = map(int, input().split())
order = list(map(int, input().split()))

start, end = 0, max(order)

print(binary_search(order, m, start, end))

위의 문제와 같은 파라메트릭 서치 문제 유형은 이진 탐색을 재귀적으로 구현하지 않고 반복문을 이용해 구현하면 더 간결하게 풀 수 있다.

 

 

---

빠르게 입력 받기 

이진 탐색 문제는 입력 데이터가 많거나, 탐색 범위가 매우 넓은 편이다. 예를 들어 데이터의 개수가 1,000만 개를 넘어가거나 탐색 범위의 크기가 1,000억 이상이라면 이진탐색 알고리즘을 의심해 보아야한다. 

 

이렇게 수 많은 데이터를 입력 받을 때 input() 함수를 사용하면 동작 속도가 느려서 시간 초과로 오답 판정을 받을 수도 있다. 때문에 이처럼 입력 데이터가 많은 문제는 sys 라이브러리의 readline() 함수를 이용하면 시간 초과를 피할 수 있다.  다음 코드는 관행적으로 암기하여 사용하도록 하자. 

 

import sys

# 하나의 문자열 데이터 입력 받기
input_data = sys.stdin.readline().rstrip()

# 입력 받은 문자열 그대로 출력
print(input_data)

# result
Hello, coding test!
Hello, Coding test!