Hoon222y

LIS(Longest Increasing Subsequence) 알고리즘이란 번역하자면 최장 증가 수열이다.예를들어 1,4,6,2,3,4,9,8 이런 수열이 있다고 하면 이 수열의 LIS는 1,2,3,4,8이 될 것이다. 이러한 LIS알고리즘을 구현하는 방법은 크게 2가지가 있는데 1) O(N^2)의 방법2) O(N*logN)의 방법 으로 나누어 볼 수 있다. 먼저 O(N^2)의 방법이다. 가장 간단하고 직관적으로 알 수 있는 방법으로 자기 자신을 기준으로 자신 앞에 있는 모든 수를 다 확인해보는 방법이다. 주어진 수열에서 개수를 x는 1~x-1까지의 모든 수열중 자신보다 작은 개수의 최대값 +1을 해주는 과정이다. 또한 최장 증가 수열에 포함되는 수들을 확인하기 위해서는 해당 그림처럼 각각의 개수를 저..