LIS 개념 증가하는 부분 수열에 대해서 먼저 설명하자면 한 배열에서 어떤 원소들을 지웠을 때 나머지 모든 원소들이 증가하는 형태를 나타내는 것을 말합니다. [1, 3, 2, 4]라는 배열이 있다고 가정하겠습니다. 그럼 증가하는 부분 수열은 [1, 3], [1, 3, 4], [1, 2, 4] 등이 나올 수 있습니다. 이런 부분 수열 중에서 가장 긴 수열을 LIS라고 합니다. LIS 알고리즘 LIS를 구현하는 알고리즘은 다음과 같습니다. 다른 모든 원소들을 비교하는 O(N^2) 알고리즘 이진 탐색으로 원소들을 비교하는 O(NlogN) 알고리즘 N^2 알고리즘 이 알고리즘은 각 원소마다 해당 원소를 마지막 원소로 가진 LIS 길이를 구합니다. 이 길이중에서 가장 긴 길이가 전체 LIS길이가 됩니다. 각 원소..