최대증가부분수열

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

1. 개념 🌠 최장 증가 부분 수열(LIS - Longest Increasing Subsequence)이란 임의의 수열로 만든 부분 수열 중 오름차순으로 정렬된 가장 긴 수열을 의미한다. '3 2 6 4 5 1'이 있다고 하자. 해당 수열의 부분 수열은 {3}, {2}, {6},... {3, 2}, {2, 1},... {2, 6, 4}, {2, 4, 5},... {3, 2, 5, 1},... {2, 6, 4, 5, 1},... {3, 2, 6, 4, 5, 1} 등이 존재한다. 여기서 최장 증가 부분 수열은 {2, 4, 5}이며 그 길이는 3이 되게 된다. 이번 글을 통해 최장 증가 부분 수열의 길이를 구하는 3가지 방법을 알아보자. 순서는 시간복잡도가 큰 것에서부터 작은 것으로 진행된다. 2. 방법 1 ..