반응형 lower_bound 썸네일형 리스트형 [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는 이진 .. LIS (Longest Increasing Subsequence) - 최장 증가 부분 수열 주어진 수열에서 을 구하는 문제 유형을 알아보자. 사실 이 유형은 DP(Dynamic Programming) 문제로 자주 나오는 유형이며, O(N^2)의 시간복잡도를 갖는 알고리즘과 O(NlogN)의 시간 복잡도를 갖는 알고리즘이 있다. (당연히 어려운 문제로는 NlogN을 요구하는 문제가 나온다...) [개념] LIS의 개념은 단어 그대로 가장 긴 증가하는 부분 수열을 구하는 것이다. 어떠한 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 '부분 수열'이라고 하며, 이 수열이 오름차순을 유지하면 '증가하는 부분 수열'이 되는 것이다. 그러므로 어떤 수열에서 만들 수 있는 부분 수열 중에서 가장 길면서 오름차순을 유지하는 수열이 LIS이다. 예를 들어 위와 같은 길이가 8인 수열이.. 이전 1 다음
