지민 개발 블로그

알고리즘 분류)이분탐색, 매개 변수 탐색*매개 변수 탐색(Parametric Search): 이분 탐색을 사용하여 조건을 만족하는 최대값을 구하는 방법이다.*Parametric Search의 Detail은 https://stopmin.tistory.com/31 여기 정리해 놨음. Solution)이진탐색의 정의에 맞게 일단 비교해야 하는 값들을 sorted해서 House에 정리해줬다.start, end 포인트를 1과 가장 멀리 떨어져있는 집 사이의 거리로 설정했다. 그리고 이제 while (start 일단 기준점이 필요하다. house[0]을 기준으로 삼고, 일단 최소 거리 1이니 count = 1로 잡는다.그리고 for문을 돌린다. 집의 개수까지 돌리는데 만약 집의 거리가 기준점+중간값 보다 크거나 같..

파라메트릭 서치는 최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다.'원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제'에 주로 파라메트릭 서치를 사용한다. 이 풀이의 아이디어는 '현재 상황에서 조건을 만족할 수 있는가?'를 확인한 뒤 조건의 만족 여부('Yes' or 'No)에 따라서 탐색 범위를 좁혀서 해결할 수 있다. 이 범위를 좁힐 때에 이진 탐색의 원리를 이용하여 절반씩 탐색 범위를 좁혀나간다.