BinarySearch
-
이분 탐색Algorithm/Algorithm 2022. 8. 30. 19:44
Binary search(이분탐색) 정렬 되어 있는 리스트에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하게 되면 O(N) -> 범위를 줄반씩 줄여 O(logN)으로 탐색 일반적으로는 Start , End , Mid 를 사용하여 탐색 ( Merget Sort 처럼 ) Mid 값을 주의하여 무한루프 주의! bisect library를 사용하여도 된다. 1) Parametic search 최적화 문제를 결정 문제로 변형 이분탐색 수행 일반적으로 도출 되는 함수는 Linear 해야 한다! (증가 및 감소 함수) 2 ) BOJ 1654번 (최적화) N개를 만들 수 있는 랜선의 최대 길이? (결정)길이가 X인 경우에 랜선이 N개 이상인지 아닌지 여부 랜선의 길이를 이분탐색하여 N일 때의 최대값을 구할..