백준에서 lower_bound, upper_bound는 정렬된 배열에서 상당히 많이 썼습니다. 파이썬에는 없을까요? bisect 모듈에는 bisect_right와, bisect_left가 있습니다. 쉽게 말해서 이 둘은 정렬된 list에서 upper_bound와 lower_bound에 대응되는데요. 어떻게 동작하는지 보겠습니다. 키가 정수인 경우에 대해서 생각해 보겠습니다. 먼저, 전자부터 보겠습니다. 일단 lo와 hi는 탐색 범위를 의미합니다. 배열 전체를 탐색하려는 경우에는 a와 x를 넣습니다. 여기서 a는 list이고 x는 기준 값을 의미해요. 여기서, 우리는 어떻게 범위를 좁히는지 볼 필요가 있는데요. a[mid]보다 x가 작으면 hi가 mid가 됩니다. 즉, 찾으려는 수 보다 a[mid]가 큰 ..
lower_bound 검색 결과
해당 글 2건
파이썬 bisect_right bisect_left : 각각 upper_bound lower_bound에 대응된다.
레퍼런스/예제
2021. 3. 19. 03:08
lower_bound, upper_bound 함수 : 정렬이 되어 있다면 쓸 수 있다.
이분 탐색을 할 때 유용한 2가지 함수를 소개해 드리고자 합니다. c++의 헤더에는 lower_bound 함수가 있어요. 그리고 upper_bound 함수가 있는데요. random 접근이 가능한 경우, O(log)에 수행하게 해 주는 함수입니다. lower_bound(first_iter,last_iter,key); upper_bound(first_iter,last_iter,key); 대충 요약하면 [first_iter, last_iter)에 대해서, key값보다 크거나 같은 최초의 위치, key 값보다 큰 최초의 위치를 리턴하는데요. iterator를 리턴해요. 위치를 리턴한다는 것입니다. 물론, Object를 lower_bound, upper_bound를 써야 할 경우도 종종 있는데요. 이러한 경우, ..
레퍼런스/예제
2019. 7. 25. 18:13
최근댓글