최장 증가 수열(LIS) 정리

최장 증가 수열 (LIS)

Longest Increasing Subsequence, 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 합니다.

{6, 2, 5, 1, 7, 4, 8, 3}이라는 배열이 있을 경우, LIS는 {2, 5, 7, 8}이 됩니다.
{2, 5}, {2, 7} 등 증가하는 부분 수열은 많지만 그 중에서 가장 긴 것이 {2, 5, 7, 8} 입니다.

 

1.  가장 긴 증가하는 부분 수열 (1 ≤ N ≤ 1,000)

가장 긴 증가하는 부분수열 길이 구하기, 2중 for 문 DP

[11053] 가장 긴 증가하는 부분수열 (LIS)

 

2.가장 긴 증가하는 부분 수열 2 (1 ≤ N ≤ 1,000,000)

가장 긴 증가하는 부분수열 길이 구하기, 이분탐색

[12015/12738번] 가장 긴 증가하는 부분 수열2,3 (LIS, 이분탐색)

 

3. 가장 긴 증가하는 부분 수열 5 (1 ≤ N ≤ 1,000,000)

가장 긴 증가하는 부분수열과 그 길이 구하기, 이분탐색

[14003번] 가장 긴 증가하는 부분 수열5 (LIS, 이분탐색)

 

4. 줄 세우기 (1 ≤ N ≤ 200)

[2631] 줄 세우기 (2중 for문)

[2631] 줄 세우기 (최장증가수열, LIS, 이분 탐색)

 

5. 줄세우기 (1 ≤ N ≤ 1,000,000)

연속최장증가수열

[7570] 줄세우기 (연속 최장 증가 수열, LIS)