20220705 TIL

Parametric Search

• 최적화 문제 (문제 상황을 만족하는 특정 변수의 최대/최솟값을 구하는 문제)를 결정 문제로 바꾸어 푸는 것
• 문제를 풀어나가는 모습이 이분 탐색과 매우 흡사함
• Parametric Search 문제임을 눈치 채기가 어렵고, DP나 그리디같은 문제와 결합을 해서 나오는 경우도 많음
• 어려우니까 예제 ㄲ
  • 스테디 셀러급 문제 BOJ 1654 : 랜선 자르기
  • (최적화문제) N개를 만들 수 있는 랜선의 최대 길이는 ?
  • (결정 문제) 랜선 길이가 x일 때 랜선의 개수가 N개 이상인가 ? (Yes or No)
  • 구해야하는 답이 인자로 들어가서 조건의 참/거짓 여부를 판단하는 문제로 바꾸기
  • 답 : 개수가 N개 이상인 지점에서 가장 긴 지점
    • 랜선의 길이가 mid일 때, 랜선의 개수가 N개 미만 : end = mid - 1
    • 랜선의 길이가 mid일 때, 랜선의 개수가 N개 미만 : start = mid + 1
  • 최대 길이를 구하는 문제에서 랜선의 길이가 X일 때 조건을 만족하는지 확인하는 문제로 변형
• (주의) 이분 탐색을 가지고 문제를 풀려면 구해야할 변수 x를 가지고 함수를 만들었을 때, 해당 함수가 증가 혹은 감소 함수이어야 함.
• Tip. 문제에서 최소/최대 얘기가 있거나 범위가 무지막지하게 크거나 뭔가 값 하나를 로그로 잘 떨구면 될 것 같을 때 PS 쓰면된다

갓킹독의 강의를 듣고 그나마 감을 잡은 듯 ㅜㅠㅠㅠㅠ

reference

https://sarah950716.tistory.com/16
https://www.youtube.com/watch?v=3TkaOKHxHnI&t=6s