[개념] 최장 증가 부분 수열, LIS(Longest Increase Subsequence) 알고리즘

BOJ의 "Q25543 - X만들기"를 풀이하다가 LIS에 대해 알게 되었고

공부한 내용을 기록하고자 한다.!!

이 키워드 몰랐으면 못 풀었을 것 같ㄷ아................

https://angxxu.tistory.com/46

[BOJ][Java] Q25543 - X 만들기

---

LIS(Longest Increase Subsequence)란?

최장 증가 부분수열 알고리즘이다.

말 그대로 가장 긴 증가하는 부분 수열을 구하는 것이다.

특정 수열이 주어졌을 때, 일부 원소를 선택해서 만든 '증가하는' 수열 중,  '가장 긴' 수열을 구하는 것!

 

LIS의 길이를 구하는 첫 번째 방법, DP  - O(n^2)

가장 간단하다.

dp배열을 만든 후, 그 위치에서 가질 수 있는 가장 긴 증가하는 수열의 길이 값을 저장해준다.

 

1.  dp[i]의 값을 1로 초기화

2.  i보다 앞에 있는 원소들을 돌면서, 그 원소가 i번째 원소보다 작을 경우(걔 뒤에 i 원소를 붙여줄 수 있을 경우)
둘 중 더 큰 값을 저장해준다.

•  앞에 있는 원소가 가지는 dp값 + 1
• 기존의 dp[i]값

for (int i = 0; i < n; i++){
	length[i] = 1;
    for (int j = 0; j < i; j++){
        if(arr[j] < arr[i]){
            length[i] = max(length[i], length[j] + 1);
        }
    }
}

3.  dp에 저장된 값 중 가장 큰 값이 LIS의 길이이다.

 

그러나, 시간복잡도가 O(n^2)이므로, n이 10000보다 커지면 1초 이상 소요된다.

 

LIS의 길이를 구하는 두 번째 방법, 이분탐색 - O(nlog(n))

dp 알고리즘에서 이전 원소들을 탐색하는 과정을 lower_bound를 이용해 시간을 줄여줄 수 있다.

O(n) -> O(logN)

LIS 배열을 만들어 놓고, LIS를 유지하기 위한 최적의 위치에 원소를 삽입하는 방식이다.

핵심 아이디어는, LIS의 가장 뒤에 가능한 작은 원소가 와야 LIS가 길어지기에 유리하다는 것이다.

 

현재 삽입하려는 원소가

LIS의 가장 뒤 원소보다 크면 그 뒤(마지막 자리)에 추가하고,

아닐 경우, 이분 탐색을 통해 그 원소보다 처음으로 커지는 자리에 원소를 넣는다.

 

정확한 LIS를 구하는 것은 아니다.

ex) 3 5 2 6 1 배열이 주어졌을 경우,

1. [3]

2. [3, 5]

3. [2, 5]

4. [2, 5, 6]

5. [1, 5, 6]

이처럼 실제로 LIS는 [3, 5, 6]이겠지만,

결론적으로 만들어질 수 없는 부분수열인 [1,5,6]이 만들어지게 된다.

 

---

cf)

https://rebro.kr/33

https://chanhuiseok.github.io/posts/algo-49/

알고리즘 - 최장 증가 부분 수열(LIS) 알고리즘

LIS (Longest Increasing Subsequence) - 최장 증가 부분 수열