수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
https://www.acmicpc.net/problem/14003
O(nlogn) 시간 복잡도로 LIS를 찾는 데 사용할 수 있는 알고리즘이 있습니다. 이 알고리즘은 이진 탐색을 사용하여 가장 긴 증가하는 부분 수열의 길이를 찾습니다.
이 알고리즘은 먼저 크기 n + 1의 벡터 dp를 생성합니다. 여기서 dp[i]는 인덱스 i에서 끝나는 가장 긴 증가하는 부분 수열의 길이를 저장합니다. 그런 다음 dp[0]을 0으로 초기화합니다.
다음으로 왼쪽에서 오른쪽으로 a의 요소를 반복합니다. 각 요소 a[i]에 대해 이진 탐색을 사용하여 dp[i]보다 크거나 같은 값이 dp에 있는지 확인합니다. dp에 그런 값이 있으면 dp[i]를 dp[i]와 해당 값의 합으로 업데이트합니다.
a의 모든 요소를 반복한 후 dp[n] 요소에는 가장 긴 증가하는 부분 수열의 길이가 저장됩니다. 그런 다음 dp를 사용하여 가장 긴 증가하는 부분 수열을 재구성할 수 있습니다.
마지막으로 가장 긴 증가하는 부분 수열의 길이와 가장 긴 증가하는 부분 수열 자체를 출력합니다.
def longest_increasing_subsequence(a):
n = len(a)
dp = [0] * n
for i in range(1, n):
j = bisect.bisect_left(dp, a[i])
dp[j] = max(dp[j], dp[j - 1] + 1)
return max(dp)
if __name__ == "__main__":
n = int(input())
a = list(map(int, input().split()))
print(longest_increasing_subsequence(a))이 코드는 먼저 크기 n + 1의 벡터 dp를 생성합니다. 여기서 dp[i]는 인덱스 i에서 끝나는 가장 긴 증가하는 부분 수열의 길이를 저장합니다. 그런 다음 dp[0]을 0으로 초기화합니다.
다음으로 왼쪽에서 오른쪽으로 a의 요소를 반복합니다. 각 요소 a[i]에 대해 이진 탐색을 사용하여 dp[i]보다 크거나 같은 값이 dp에 있는지 확인합니다. dp에 그런 값이 있으면 dp[i]를 dp[i]와 해당 값의 합으로 업데이트합니다.
a의 모든 요소를 반복한 후 dp[n] 요소에는 가장 긴 증가하는 부분 수열의 길이가 저장됩니다. 그런 다음 dp를 사용하여 가장 긴 증가하는 부분 수열을 재구성할 수 있습니다.
마지막으로 가장 긴 증가하는 부분 수열의 길이를 출력합니다.
