알고리즘 공부 : LIS
과학고에서 떨어진 나는 그동안 충격에 휩싸여 열심히 하지 않아 실력이 많이 줄었을거라 생각되니 더 열심히 재활 활동을 꾸준히 해보자. 소개할 알고리즘 : LIS LIS는 Longest Increasing Subsequence, 즉 최장 증가 부분 수열을 말한다. *) 예를 들어 {10,20,10,30,20,50}이라는 배열이 있다고 가정하자. 그렇다면 이 배열에서의 LIS는 {10, 20, 10, 30, 20, 50} => {10, 20, 30, 50} 이러한 상태가 된다. 이 LIS 알고리즘은 우리에게 특정한 배열에서의 LIS를 구해주는 알고리즘이다. 이 알고리즘에는 3가지 방법이 있다. 1. O(n^2) DP 2. O(n log n) Segment Tree 사실상 거의 안씀 3. O(n log n) ..
2020.12.25