반응형 Binary search 썸네일형 리스트형 [C++] lower_bound & upper_bound STL에서 제공하는 lower_bound와 upper_bound에 대해서 알아보자. LIS(Longest Increasing Subsequence)를 공부하다가 알게 된 개념이다. 필자 개인적으로는 STL에 대해서 잘 몰랐는데, 처음으로 STL이 매우 유용하다는 것을 깨닫게 해준 함수이다. (이를 계기로 계속 STL을 이용하려고 노력중이다) 우선 lower_bound와 upper_bound는 이진 탐색(Binary Search)을 기반으로 탐색하는 함수이다. 따라서 배열이나 리스트, 벡터 등이 기본적으로 정렬이 되어있어야 하고, 시간복잡도는 O(logn)이다. 기본적으로 이진 탐색은 찾고자 하는 원소가 있는지, 있다면 어디에 위치해 있는지를 찾는다면, lower_bound와 upper_bound는 이진 .. 이전 1 다음
