LIS(Longest Increasing Subsequence)

1. LIS 개념

Longest Increasing Subsequence 의 약자이며 우리말로는 최장 증가 부분 수열이라 한다. 즉, 주어진 배열에서 가장 긴 증가하는 부분 수열을 찾는 문제이다..

2. 단순한 구현 방법

시간 복잡도: O(N^2)

일차원 배열이 주어졌을 때 각 원소를 순회하며, 그 원소를 기준으로 자신 보다 앞에 위치한 작은 수 중 가장 긴 길이에 자기 자신에 해당하는 1을 추가하여 cache에 기록한다. 이렇게 순회를 마쳤다면 cache에 기록되어 있는 수 중 최대값을 출력한다면 LIS의 길이가 된다.
cache[i] :: i번째 수를 마지막 원소로 하는 LIS 의 길이 로 정의된다.
단점: 시간복잡도가 O(N^2) 이며, LIS의 길이만 구할 수 있기 때문에 한계가 존재.

3. 개선된 구현 방법

시간복잡도: O(NlogN)

이분 탐색을 이용한 풀이방법
이전과 같이 배열을 순회하지만 이분탐색을 이용하여 LIS를 유지하기 위한 최적의 위치에 수를 삽입한다. 순회를 할 때 O(N), 자리를 찾는데 lower_bound를 사용하므로 O(logN)이 걸리므로 총 O(NlogN) 시간복잡도를 갖는다.

처리 과정

• 0. lis 배열을 만들고 배열에 올 수 없는 최소값(-INF) 1개를 원소로 갖게 한다.
• 1. 주어진 arr배열을 순회한다.
  • 1.1. 현재 요소가 lis 배열 맨 뒤 요소보다 크다면
    • 1.1.1. lis 배열에 현재 요소를 추가한다.
  • 1.2. 현재 요소가 lis 맨 뒤 요소보다 작거나 같다면
    * 1.2.1. lis 배열에서 lower_bound를 통해 위치(index)를 찾는다.

    * 1.2.2. lis[index]를 현재 요소로 변경해준다.

    ===================================
    이때 최종 lis의 배열 원소들은 LIS가 아닐 수 있다. lis 배열의 길이가 LIS의 길이와 같을 뿐이다

4. 결론

• lis 배열의 길이가 곧 우리가 구하는 LIS 값이 된다.
• O(NlogN)의 시간 복잡도로 LIS를 구할 수 있다.

+추가로 공부할 부분

• 종만북 LIS 부분
• 이전 알고리즘 수업에서 배웠을 때 어떻게 배웠는지 다시 찾아볼 것