-
이분탐색 3 - LIS (Longest Increasing Subsequence), 백준 12105알고리즘 2024. 3. 2. 21:28
#include <iostream> using namespace std; int main(int argc, const char * argv[]) { ios::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; int arr[n]; int now = 0; cin >> arr[0]; for (int i = 1; i < n; i++) { int num; cin >> num; if (num > arr[now]) { now++; arr[now] = num; } else { int start = 0, end = now, mid = 0; int result = 0; while (start <= end) { mid = (start + end) / 2; if ( arr[mid] >= num ) { result = mid; end = mid - 1; } else { start = mid + 1; } } arr[result] = num; } } cout << now + 1; return 0; }
증가하는 형태의 부분 수열 중 가장 긴 것의 길이를 구하는 방법
O(nlog(n)) : 한 바퀴 탐색 * 이분탐색
50 60 70 55 이런 순서의 수열이 있으면
50
50 60
50 60 70
까지는 증가하는 형태니까 그냥 추가해주고, 55가 올 때는 55보다 큰 값 중 제일 차이가 적은 값과 교체
-> 50 55 70
왜 굳이 바꾸어야 하느냐? 그냥 버리면 안되나?
50 60 70 55 60 65 70 80 90
수열이 이렇게 되어 있다고 가정했을 때, 그냥 버리면 50 60 70 80 90으로 길이가 5가 되는데,
50 55 60 65 70 80 90의 7 크기의 길이를 잃게 됨
50 60 70
50 55 70
50 55 60
50 55 60 65 70 80 90
이 순서로 진행됨
주의할 점은 길이를 구하는 거지 정확한 LIS를 구하는 건 아님
'알고리즘' 카테고리의 다른 글
스택 응용, 백준 9935: 문자열 폭발 (0) 2024.03.05 에라토스테네스의 체 (0) 2024.03.04 이진탐색 2 - Parametric Search, 백준 1654 (0) 2024.03.02 이분 탐색(binary search) (0) 2024.02.25