[알고리즘] LIS(Longest Increasing Subsequence) 최장증가수열 #1

요즘 LIS 알고리즘을 공부하고 있다.

나이들어 알고리즘을 공부하려니 머리가 따라가질 않는다...ㅜㅜ

대학원생 시절 하필 알고리즘 과목이 영어 강의였던게 한으로 남는다.

LIS는 Longest increasing subsequence의 약자이다.

우리말로는 최장증가수열이라고 한다.

이렇게 말로는 이해가 안되고

예를 들어 다음과 같은 수열이 있을때

{3,1,2,4}

최장증가수열은 

{1,2,4} 가 된다.

이렇게 주어진 수열에서 점진적으로 숫자가 커지는 수열을 최장증가수열이라고 한다.

이걸 사람이 눈으로 구하는 것은 매우 쉽다.

아마 그냥 딱 보면 나올 것이다.

하지만 수열이 길어진다면 쉽지 않을 것이다.

그래서 우린 프로그래밍을 해야한다.

주어진 수열에서 최장증가수열을 구하는 알고리즘은

n^2과 nlogn 방식이 있다.