upper_bound 검색 결과

해당 글 3건
파이썬 bisect_right bisect_left : 각각 upper_bound lower_bound에 대응된다.

백준에서 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]가 큰 ..
레퍼런스/예제 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
삽입 정렬 알고리즘 : 원소가 들어갈 위치는 어디인가?

정렬 알고리즘 시리즈를 쓰려고 합니다. 총 20 ~ 25편 정도로 구성이 될 듯 싶습니다. 먼저 O(n^2)짜리 알고리즘 3대장을 써 볼 건데요. 아마도, 알고리즘 교재에서는 맨 처음에 나올 듯 싶습니다. 오늘은 그 중, 삽입 정렬에 대해서 알아보겠습니다. 이 글을 이해하기 위해서는 memcpy와 memmove를 이해하면 더없이 좋을 겁니다. [관련글] 메모리 복사 함수는 어떻게 쓸까요? 삽입정렬 알고리즘은 Loop를 돌면서 해당 원소가 이미 정렬된 부분 배열에서 어디로 들어가면 좋은지를 구한 다음에, 그 위치에 넣는 식으로 동작합니다. [6, 3, 4, 2, 1, 3]을 오름차순으로 정렬한다고 해 봅시다. 수가 작을수록 우선 순위가 높을 겁니다. 먼저 1회전을 돌 겁니다. 6을 선택합니다. 제가 파란색..
자료알고/알고리즘 2019. 7. 11. 11:44