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

안녕하세요? 코딩충입니다. 

뜬금없이 LIS 알고리즘을 올리는 이유는 컴퓨터 파일들을 정리하다가 나왔기 때문인 것도 있고, 

생각이 나서 그런 것도 있습니다.

LIS는 Longest Increasing Subsequence 의 약자로, 최장 증가 부분수열이라고도 합니다.

최장 증가 부분수열이 뭔지 설명을 하려면 부분수열이 뭔지 아셔야 됩니다.

원래 수열에서만 원소들을 골라서 만든 수열을 부분수열이라고 합니다.

증가 부분수열이라는 것은 첫번째 원소를 제외하고 모든 원소는 자기 앞의 원소보다 커야 된다는 것이죠.

여기서 중요한 것은 "커야 된다" 라는 것입니다. 문제마다 다르기는 하지만 원래 LIS는 증가해야 됩니다. 

같으면 안됩니다.

그래서 최장 증가 부분수열은 결국 수열의 부분수열 중 증가하는 부분수열중 가장 긴 부분수열(또는 길이)입니다.

다시 말하자면 수열의 부분수열 중 증가하는 부분수열 중 가장 긴 증가하는 부분수열(또는 길이)입니다.]

이제 LIS가 뭔지 이해 하셨으리라고 믿고, LIS를 구하는 방법에 대해 알려드리겠습니다.

LIS를 구하려면 DP를 이용해야 하는데 [알고리즘] 동적계획법(Dynamic Programing, DP) 에 포함하지 않은 이유는 DP가 뭔지만으로는 이런 문제를 풀기 힘들기 때문입니다. 앞으로도 다른 알고리즘에 포함되는 세분화된 알고리즘에 대해 포스팅 할 생각입니다. 

이 알고리즘으로 정확히는 LIS의 길이를 구하겠지만 LIS 그 자체도 구할 수 있습니다.

아래의 사진은 제가 처음 LIS에 대해서 배웠을때 정리해 놓은 것인데 이해하기 힘드실수도 있으나, 도움이 될 수도 있을 것 같아서 올립니다.

asing Subsequence) - Tistory

CONTENT BY 코딩충