[Algorithm] LIS(Longest Increasing Subsequence; 최장 증가 부분 수열)

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

어떠한 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 찾는 문제

이때, 부분 수열은 서로 연속할 필요는 없다. 

 

어떠한 수열에서 일부 원소를 선택해 새로 만든 수열은 '부분 수열'이며 그 수열이 오름차순으로 정렬되어 있으면 '증가하는 부분 수열'이다.

 

ex)

수열 [10, 20, 10, 30, 20, 50] 

해당 수열에서 [10, 20, 30, 50], [10, 20, 50], [10, 50],... 등 많은 증가 부분 수열이 있지만 

많은 증가 부분 수열 中 가장 길이가 긴 수열은 4개의 원소를 가진 [10, 20, 30, 50]이다. 따라서  [10, 20, 30, 50]  최장 증가 부분 수열이다. 

 

LIS는 DP(Dynamic Programming)문제 유형으로 자주 나온다. 

 

• 시간 복잡도

DP를 이용한 방법 : O(N^2)

이분 탐색을 이용한 방법 : O(NlogN)

 

• DP(Dynamic Programming)

[Algorithm] Dynamic Programming(동적 계획법, 다이나믹 프로그래밍)

 

• LIS 문제 예제

[백준(Baekjoon)] 11053 가장 긴 증가하는 부분 수열