SY DevLog

저번 글에서는 최장 증가 수열의 길이를 구하는 경우에 대해 다루었다. LIS(Lowest Increasing Subsequence) - 길이 구하기 LIS(Lowest Increasing Subsequence) : 최장 증가 수열 : 어떤 수열이 주어졌을 때, 그 수열에서 가장 긴 증가하는 부분 수열을 구하는 알고리즘 (최장 증가 수열의 요소가 꼭 연속하지 않아도 됨) 1. 최장 lotuslee.tistory.com 이분탐색을 이용하여서 새로 입력받은 수가 리스트에 들어갈 위치를 구하였다. 그러나 이 알고리즘은 최장 증가 수열의 길이를 구할 수는 있지만 수열 자체를 구할 수는 없었다. (위의 포스팅 참고) 예를 들어, 다음과 같은 반례가 있다. 수열 10 30 50 20 60 이 있다고 할 때 위의 알고..

LIS(Lowest Increasing Subsequence) : 최장 증가 수열 : 어떤 수열이 주어졌을 때, 그 수열에서 가장 긴 증가하는 부분 수열을 구하는 알고리즘 (최장 증가 수열의 요소가 꼭 연속하지 않아도 됨) 1. 최장 증가 수열을 나열하는 문제 2. 최장 증가 수열의 길이를 구하라는 문제 보통 이 두가지 문제가 기본적이다. 여기서는 최장 증가 수열의 길이를 구하는 알고리즘을 볼 것이다. 1번 케이스의 경우, 수열 자체를 구하는 것이기 때문에 수열 요소의 추적이 별도로 필요하다. 시간 복잡도 : O(NlogN) 대략적인 알고리즘은 아래와 같다. 증가하는 수열을 저장하는 리스트가 필요하다. 리스트는 증가하는 수열을 저장하고 있기 때문에 계속 오름차순 상태를 유지하면서 갱신된다. 수열의 요소를..