[CS지식] 최장 증가 수열 (Longest Increasing Sequence)

최장 증가 수열 문제는 동적 계획법으로 풀 수 있는 유명한 알고리즘 문제이다.

정의

어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 말한다.

예시

3 5 7 9 2 1 4 8 에서 몇 개의 수를 제거해 부분수열로 만들어보자

3 7 9 1 4 8 (5, 2 제거) → 일부가 오름차순으로 정렬

7 9 1 8 (3, 5, 2, 4 제거) → 일부가 오름차순으로 정렬

3 5 7 8 (9, 2, 1, 4 제거) → 전체가 오름차순으로 정렬 (LIS)

1 4 8 (3, 5 , 7, 9 , 2 제거) → 전체가 오름차순으로 정렬

→ 증가 부분 수열

→ 이 중 가장 긴 증가하는 부분 수열을 ‘최장 증가 수열(LIS)’라고 한다.

한 수열에서 여러 개의 LIS가 나올 수도 있다.

구현방법 (시간복잡도)

1. DP 활용 : O(N^2)

• 일반적으로 최장 증가 부분 수열의 길이가 얼마인지 푸는 간편한 방법은 DP를 이용 주어진 배열에서 인덱스를 한 칸씩(k+=1) 늘려가면서 확인합니다. 그리고 내부 반복문으로 k보다 작은 인덱스들을 하나씩 살펴 보면서 arr[i] < arr[k]인 것이 있을 경우, length[k] 를 업데이트 합니다.
• for (int k= 0; k< n; k++){ length[k]= 1; for (int i= 0; i< k; i++){ if(arr[i]< arr[k]){ length[k]= max(length[k], length[i]+ 1); } } }
• 아래에서 length[i]는 i번째 인덱스에서 끝나는 최장 증가 부분 수열의 길이를 의미합니다.

1. Lower Bound : O(NlogN)

• 이진 탐색 방법을 기반으로 사용LIS의 형태를 유지하기 위해 주어진 배열의 인덱스를 하나씩 살펴보면서 그 숫자가 들어갈 위치를 이진탐색으로 탐색해서 넣습니다.
• 이분탐색은 일반적으로 시간복잡도가 O(log n) 이라고 알려져 있으므로, 이 문제의 시간 복잡도를 O(nlog n)으로 개선시킬 수 있게 됩니다.
• 시간 복잡도를 개선하기 위해 LIS를 구성할 때 이진탐색을 활용합니다.

 

면접질문

1. LIS라고 하는 최장 증가 수열은 무엇인가요?

• 임의의 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있습니다. 이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 말합니다.

1. 수열 10 20 1 2 3 4 8 6 이 있을 때 최장 증가 수열의 길이는 몇인가요?

• 부분수열1 2 3 4 6로 5입니다