![]()
알고리즘 분류) 이분탐색, 매개 변수 탐색 *매개 변수 탐색(Parametric Search): 이분 탐색을 사용하여 조건을 만족하는 최대값을 구하는 방법이다. *Parametric Search의 Detail은 https://stopmin.tistory.com/31 여기 정리해 놨음. Solution) 이진탐색의 정의에 맞게 일단 비교해야 하는 값들을 sorted해서 House에 정리해줬다. start, end 포인트를 1과 가장 멀리 떨어져있는 집 사이의 거리로 설정했다. 그리고 이제 while (start count += 1로 간다. 그리고 if count 가 C보다 커질 경우에는 (start+end)값이 작기 때문이기에 start point를 mid + 1로 바꿔준다. 그리고 result = mid..
파라메트릭 서치는 최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다. '원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제'에 주로 파라메트릭 서치를 사용한다. 이 풀이의 아이디어는 '현재 상황에서 조건을 만족할 수 있는가?'를 확인한 뒤 조건의 만족 여부('Yes' or 'No)에 따라서 탐색 범위를 좁혀서 해결할 수 있다. 이 범위를 좁힐 때에 이진 탐색의 원리를 이용하여 절반씩 탐색 범위를 좁혀나간다.
![]()
이진탐색이 시간초과 해결의 Point였다. 처음에 이 문제를 우당탕탕 풀었을 때는 Case의 답 중 가장 큰 값에서 -1씩 해서 모두 돌려보는 과정으로 이 문제를 해결해보았다. 그러나 시간초과가 나왔다. 다른사람들 코드를 구경하다보니, start,end,mid가 있길래 '어 이거 이진탐색문항이구나..' 깨닫게 되었다. 알고보니 이진탐색을 활용하면 빠르게 풀이되는 문항이었다. 이진탐색은 https://stopmin.tistory.com/28 에 간단하게 정리해두었다! 내가 처음 짠 코드들은 둘 다 순차탐색을 활용한 코드였기에 시간초과가 나올 수 밖에 없었다. 내가 처음 짠 2개의 시간초과 코드들) import sys K, N = map(int,sys.stdin.readline().split()) strin..
이진 탐색이란, 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘이다. 이진탐색 vs 순차탐색 1) 순차탐색 순차탐색이란, 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 즉, 이진탐색과는 구분되는 방법이다. 순차탐색은 주로 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용된다. 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소를 찾을 수 있다는 장점이 있다. 구현도 매우 간단하다. /*논외로, 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드를 이용할 때도 내부에서는 순차 탐색이 수행된다.*/ 2) 이진탐색 이진탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 이진 탐..
