Algorithm/Algorithm
이분 탐색
Dortmoot
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일 때의 최대값을 구할 수 있도록 설정
3) BOJ 2295번
- 일반적인 IDEA = i , j , k , l 값을 모두 한번씩 사용하여 O(N^4) 에 탐색
- 이분탐색을 이용하면 O(N^3logN )
- i , j 와 k , l 값을 비교하는 방식으로 처리하게 되면 O(N^2)에 대해서 이분탐색 O(N^2log(N^2)) = O(N^2 * 2logN ) 처리 가능