20220705 TIL

juheesvt·2022년 7월 5일
0

TIL

목록 보기
2/2
  • 최적화 문제 (문제 상황을 만족하는 특정 변수의 최대/최솟값을 구하는 문제)를 결정 문제로 바꾸어 푸는 것
  • 문제를 풀어나가는 모습이 이분 탐색과 매우 흡사함
  • 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

profile
Computer Science, Kookmin Univ. WSUG web developer

0개의 댓글