SY DevLog

백준 전깃줄 문제와 유사하다. 이진탐색을 사용한 증가하는최장부분수열(LIS)을 구하는 문제이다. 다만, 수열의 길이만 구하는 것이 아니라 수열 자체도 구해야 하므로 역추적하는 배열이 별도로 필요하다. 역추적을 통한 증가하는최장부분수열의 수열 구하는 방법은 아래 포스팅에 나와있다. LIS(Lowest Increasing Subsequence) - 수열 구하기 저번 글에서는 최장 증가 수열의 길이를 구하는 경우에 대해 다루었다. LIS(Lowest Increasing Subsequence) - 길이 구하기 LIS(Lowest Increasing Subsequence) : 최장 증가 수열 : 어떤 수열이 주어졌을 때, 그.. lotuslee.tistory.com 이 문제는 전선이 만나지 않도록 하면서 전구가 ..

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