LIS에 대해 설명해보세요.

---

LIS란?

• 원소가 N개인 배열의 일부 원소를 골라 만든 부분 수열 중에서 각 원소가 앞에 있는 원소보다 크고 그 길이가 최대인 부분 수열을 최장 증가 부분수열이라고 한다. 주어진 수열에서 LIS의 길이를 구하는 방법은 대표적으로 두 가지가 있다.

---

DP를 이용한 LIS 찾기

• 수열의 길이와 같은 LIS 배열을 만들고, 현재 위치보다 앞에 있는 원소 중에서 더 작은 값이 있다면 해당 위치의 LIS 값들 중 최댓값에 1을 더한 것이 현재 LIS 값이 된다. 없다면 1을 저장하고 끝까지 반복하면 가장 큰 LIS 값이 그 수열의 LIS 길이가 된다. 이 때 O(N^2)의 시간 복잡도를 가진다.

---

이분 탐색을 이용한 LIS 찾기

• 똑같이 수열의 길이와 같은 LIS 배열을 만들고, 원래의 수열에서 각 원소에 대해 LIS 배열에서 위치를 찾아가는 방식이다.
  
• 최종적으로 위의 배열에서 LIS의 길이는 3이라는 것을 알 수 있다. 이 때 O(NlogN)의 시간 복잡도를 가진다.

---

결론

LIS는 최장 증가 부분수열로, 한 수열 안에서 가장 긴 오름차순 부분 수열을 의미합니다. 이 LIS의 길이를 구하는 대표적인 방법으로 DP를 이용하는 방법과 이분 탐색을 이용한 방법이 있습니다. DP를 이용하여 구하게 되면 모든 원소들에 대하여 이전 결과를 모두 살펴봐야 하므로 O(N^2)의 시간 복잡도를 가지게 됩니다. 하지만 이분 탐색의 경우 앞의 결과를 모두 볼 필요 없이 처음으로 큰 값이 나오는 곳에 있는 값과 교체하는 식이므로 O(NlogN)의 시간 복잡도를 가져서 더 효율적으로 길이를 알 수 있습니다.