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

LIS

• Longest Increasing Subsequence 의 약자로, 최장 증가 부분 수열 또는 가장 긴 증가하는 부분 수열 이라고 불린다.
• 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건(오름차순)을 만족하고, 그 길이가 최대인 부분 수열을 찾는 알고리즘이다.

일반적으로 LIS의 간편한 방법에는 DP가 있다.

• DP에 대해서는 아래 게시글 참고.
• https://hoozy.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9D%B4%EB%A1%A0-12-DP-%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95

이분탐색을 이용한 LIS

• 이분탐색에 대해서는 아래 게시글 참고
• https://hoozy.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9D%B4%EB%A1%A0-11-%EC%9D%B4%EB%B6%84%ED%83%90%EC%83%89
• LIS의 형태를 유지하기 위해 주어진 배열의 인덱스를 하나씩 살펴보면서 그 숫자가 들어갈 위치를 이분탐색으로 탐색해서 넣는다.
• 이분탐색은 일반적으로 시간복잡도가 O(logn)으로 알려져 있으므로, 위의 문제를 O(blogs)의 시간복잡도로 해결할 수 있게 된다.

원리

알고리즘 문제 추천

1. 가장 긴 증가하는 부분 수열 (실버 2)

• https://www.acmicpc.net/problem/11053

2. 가장 긴 증가하는 부분 수열 2 (골드 2)

• https://www.acmicpc.net/problem/12015

2. 가장 긴 증가하는 부분 수열 3 (골드 2)

• https://www.acmicpc.net/problem/12738

2. 가장 긴 증가하는 부분 수열 4 (골드 4)

• https://www.acmicpc.net/problem/14002

참고 자료

https://velog.io/@seho100/%EC%B5%9C%EA%B0%95-%EC%A6%9D%EA%B0%80-%EB%B6%80%EB%B6%84-%EC%88%98%EC%97%B4LIS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98