Longest increasing Subsequence
Subsequence : 불연속
자연수를 받아서 Longest incresing인(같은걸 허용안하고 계속 커지는 subsequence를 찾아라)
연속이면 문제가 쉬움
불연속이라서 어려운 거임
결국 O(nlogn)으로 풀 수 있음
우선 O(n^2)풀이 부터
keypoint는 이거임
만약 입력값 x까지(x포함)의 longest increasing subsequence를 구하다면 입력값 x보다 작은 '입력값' 중에 그 입력값의 dp값(그 입력값 까지의 longest increasing subsequence)중에 제일 큰 값에서 1을 더한 값이 답이 되겠다.
여기까지의 시간복잡도는 O(n^2)의 시간이 걸린다.
*non-decreasing을 찾으라고 해도 같은 방식으로 풀릴까?
standard 테크닉이 있다.
한번 쭉 훑어서 같은 값들끼리 모을 수 있다 -> 그런 다음 같은 값을 살짝 바꾸기
만약 3이 세 개면 3, 3.1, 3.2 -> 이런식으로 바꾸는 것
그러면 다 다르게 됨
그리고 증가하는 걸 찾으면 결국 3,3,3도 찾는게 됨
같은게 있어도 같은게 없는 문제로 바뀌게 됨
그러므로 non-decreasing으로 바꾸어도 똑같이 풀림
O(nlogn)로 풀기
제일 가까운 점 찾기 문제를 회상해보면
band에 있는 것만 봤음
-> 도움이 되겠다고 생각했는데 최악의 경우(band에 모든 점이 다 들어있는 경우)에는 안되었음
이것도 마찬가지로 새로운 값이 들어왔을 때 앞에 있는 값 다 보려고 하지 않고 기억안해도 되는 걸 버릴려고 시도 -> 근본적으로는 도움이 안됨
근데 여기에 무언가를 더해주면 도움이 된다.
그리고 dp값들중에 같은 값을 보자 -> 어떤 모양일까?
결론 : 3들만 보면 같거나 내려간다는 뜻
이렇게 하면 볼 게 줄어드는 것 같지만
결국 다 봐야함
???
point : dp값이 같은 애들 중에 제일 가까운 애들만 기억하면 됨
(why? 걔가 제일 작기 때문(제일 작기도 하고 제일 가까운 거기도 하고))
그럼 이제 마지막에 기억하는 놈들만 가지고
(1중에 기억하는 놈, 2중에 기억하는 놈, 3중에 기억하는 놈, 4중에 기억하는 놈이 어떻게 생겼는지 보자)
버릴꺼 버리고 마지막것만 보자 -> 그러면 패턴을 발견할 수 있음
알 수 있는 사실 : 3높이와 4높이를 보면 4가 무조건 높음(5는 더 높을 거임)
기억하는 것들만 이렇다는 거임
기억하는 것들만 모아보면 이런식으로 간다는 이야기임
여기서 새로운 값이 들어오면
얘네들을 배열에 넣어두고 binary search를 할 수 있다!
만약 30(같은 값)이 들어오면(25 안들어왔다고 치고)
binary search해서 그냥 5가 되는 거임
60보다 크면 index8에 들어오면 됨(새로운 dp값 만듬)
3보다 작으면 0번 index에 0이 있다고 생각하면 됨
이 알고리즘이 O(nlogn)짜리 알고리즘
이렇게 하면 모든 값의 dp값을 계산할 수 있음
진짜 sequence는 어떻게 찾냐?(지금은 크기만 찾은 거)
