매개변수탐색1 [알고리즘] 이분 탐색, 매개 변수 탐색 & 백준(랜선 자르기, 나무 자르기, 공유기 설치, 히오스 프로게이머) 이분 탐색이란? 정렬된 배열에서 target의 존재 여부와 위치를 알려준다. 재귀적으로 탐색 범위를 반으로 줄여, 시간복잡도를 O(logN)까지 줄일 수 있다. 매개 변수 탐색(Parametric Search)란? 이분 탐색과 유사하다. 탐색 범위를 반으로 줄이기 때문에 시간복잡도는 O(logN)이다. 최적화 문제를 결정 문제로 바꾸어 풀 때 사용한다. - 최적화 문제: 어떤 알고리즘의 최적 솔루션을 찾는 것 - 결정 문제: 답이 이미 결정되어 있다고 보고 문제를 푸는 것 이진 탐색과 매개변수 탐색의 차이점 이진 탐색은 배열에서 target과 일치하는 값을 찾으면 바로 함수를 종료하지만, 매개변수 탐색은 함수를 종료하지 않고 모든 배열을 살펴본다. 따라서, 매개변수 탐색은 어떤 조건을 만족하는 위치 중 .. 2022. 10. 6. 이전 1 다음
