가장 긴 증가하는 부분 수열(LIS)

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길이가 됩니다.

 

각 원소들이 num배열에 담아져 있고, 각 원소를 마지막 원소로 가진 LIS길이를 DP 배열에 표시한다고 가정해보겠습니다.

이를 점화식으로 나타낸다면 이런 식이 만들어집니다.

DP[i] = max(DP[j]) + 1 (0<= j < i, num[j] < num[i])

DP[i] = 0 (i = 0)

 

해당 식을 바탕으로 num[10, 20, 10, 30, 20, 50] 배열을 가지고 DP 배열을 만든다면 DP[1, 2, 1, 3, 2, 4]가 됩니다.

이중 가장 큰 수는 4이니 num배열의 LIS 길이는 4가 됩니다.

 

이렇게 하나의 원소를 구하려면 그 전 모든 원소를 검사해야 하므로 복잡도는 N^2이 됩니다.

 

 

NlogN 알고리즘 (LIS 길이 구하기)

---

이 알고리즘을 알기 위해서 먼저 lower bound를 알아야 합니다.

lower bound는 어떠한 값 x가 정렬된 배열에서 정렬을 유지하면서 삽입될 수 있는 위치 중 가장 작은 위치를 말합니다.

 

알고리즘은 증가하는 수열인 리스트가 있다고 가정하고 다음과 같은 방식으로 진행됩니다.

• 리스트에서 원소 element의 lower bound를 찾습니다.
• lower bound가 리스트의 크기를 벗어난다면 element를 리스트의 마지막에 추가합니다.
• lower bound가 리스트 안이라면 해당 위치의 원소를 element로 교체합니다.

 

num[10, 20, 10, 30, 20, 50]을 가지고 이 알고리즘을 수행해보겠습니다.

 

[10] : 리스트에 수가 없으므로 10이 추가됩니다.

[10, 20] : 20의 lower bound는 인덱스 1이므로 리스트를 벗어나서 20을 추가합니다.

[10, 20] : 10의 lower bound는 인덱스 0이므로 10을 10으로 교체합니다.

[10, 20, 30] : 30의 lower bound는 인덱스 2이므로 리스트를 벗어나서 30을 추가합니다.

[10, 20, 30] : 20의 lower bound는 인덱스 1이므로 20을 20으로 교체합니다.

[10, 20, 30, 50] : 50의 lower bound는 인덱스 3이므로 리스트를 벗어나서 50을 추가합니다.

 

마지막 리스트의 크기가 4이므로 num배열의 LIS 길이는 4가 됩니다.

 

lower bound를 찾는 과정이 이진탐색을 통해 만들어진다면 한 원소를 찾는 시간이 logN이므로 전체 시간복잡도는 NlogN이 됩니다.

 

하지만 이 알고리즘으로 만들어지는 리스트는 LIS의 원소들이 담겨있는 리스트는 아닙니다.

그저 LIS 길이와 같은 길이를 가진 리스트일 뿐입니다. 

따라서 LIS를 구하기 위해서는 추가적인 방법이 필요합니다.

 

NlogN 알고리즘 (LIS 구하기)

---

LIS를 구하기 위해서는 num 배열의 i번째 원소를 리스트에 담을 때의 인덱스가 필요합니다.

해당 배열을 idx 배열이라고 하겠습니다.

 

전에 사용했던 num[10, 20, 10, 30, 20, 50] 배열을 이용한다면

num 인덱스 0의 10은 리스트 인덱스 0에 추가되고

num 인덱스 1의 20은 리스트 인덱스 1에 추가되고 

num 인덱스 2의 10은 리스트 인덱스 0에 갱신됩니다.

...

 

이렇게 num 배열로 idx 배열을 만든다면 idx[0, 1, 0, 2, 1, 3]이 만들어 집니다.

 

다음, 이 idx 배열의 끝에서 부터 리스트의 마지막 인덱스를 찾게 됩니다.

리스트의 마지막 인덱스는 3이므로 3을 찾고

3을 찾은 다음 그전 인덱스인 2를 찾고...

인덱스 0까지를 찾게 됩니다.

 

각각의 인덱스를 찾은 idx 배열을 보면 다음과 같습니다.

idx[0, 1, 0, 2, 1, 3]

 

이 idx 배열을 num[10, 20, 10, 30, 20, 50]과 조합하면

LIS는 [10, 20, 30, 50] 임을 알 수 있습니다.

 

References

https://seungkwan.tistory.com/8