lis 알고리즘 : lower_bound 이용해서 그리디하게 해결해 봅시다.
lis 알고리즘은, 최장 증가 수열을 구하는 알고리즘입니다. 길이가 n인 수열이 있을 때, 이것을 O(nlogn)에 구할 수 있는 방법은 일종의 그리디를 이용한 것입니다. 물론, 조금 더 어려운 응용 문제를 풀기 위해서는 세그먼트 트리라는 자료구조를 알아야 하지만, 여기에서는 논외로 하도록 하겠습니다. 먼저 전체 소스 코드를 보겠습니다. res는 최장 증가 수열의 길이를 구하기 위한 벡터입니다. v는 문제에 주어진 수열입니다. 문제에 주어진 수열 전체를 돌면서, 먼저 lo 값을 구하고 있습니다. 이 lo 값은 res에서 v[i]보다 크거나 같은 최초의 위치를 찾습니다. 그 위치가 res의 크기와 같다면, res의 뒤에 추가합니다. 그렇지 않다면, res[lo]값에 v[i]를 갱신합니다. 일단 전체 시간 ..
자료알고/알고리즘
2020. 6. 17. 02:19
최근댓글