수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
https://www.acmicpc.net/problem/14002
가장 긴 증가하는 부분 수열(LIS)은 수열의 요소를 포함하는 증가하는 수열 중 가장 긴 수열입니다. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}의 가장 긴 증가하는 부분 수열은 A = {10, 20, 30, 50}이고 길이는 4입니다.
LIS를 찾는 데 사용할 수 있는 여러 가지 알고리즘이 있습니다. 가장 일반적인 알고리즘 중 하나는 동적 프로그래밍 알고리즘입니다.
동적 프로그래밍 알고리즘은 먼저 크기 n + 1의 벡터 dp를 생성합니다. 여기서 dp[i]는 인덱스 i에서 끝나는 가장 긴 증가하는 부분 수열의 길이를 저장합니다. 그런 다음 dp의 모든 요소를 1로 초기화합니다.
다음으로 왼쪽에서 오른쪽으로 a의 요소를 반복합니다. 각 요소 a[i]에 대해 a[i] 앞의 모든 a 요소를 반복합니다. 각 요소 a[j]에 대해 a[j] < a[i]를 확인합니다. 그렇다면 dp[i]를 max(dp[i], dp[j] + 1)로 업데이트합니다. prev[i]도 j로 업데이트합니다.
a의 모든 요소를 반복한 후 dp[n] 요소에는 가장 긴 증가하는 부분 수열의 길이가 저장됩니다. 그런 다음 prev를 사용하여 가장 긴 증가하는 부분 수열을 재구성할 수 있습니다.
마지막으로 가장 긴 증가하는 부분 수열의 길이와 가장 긴 증가하는 부분 수열 자체를 출력합니다.
def longest_increasing_subsequence(a):
n = len(a)
dp = [1] * n
prev = [-1] * n
for i in range(1, n):
for j in range(i):
if a[j] < a[i]:
dp[i] = max(dp[i], dp[j] + 1)
prev[i] = j
longest = 0
idx = -1
for i in range(n):
if longest < dp[i]:
longest = dp[i]
idx = i
lis = []
while idx != -1:
lis.append(a[idx])
idx = prev[idx]
return lis먼저 크기 n + 1의 벡터 dp를 생성합니다. 여기서 dp[i]는 인덱스 i에서 끝나는 가장 긴 증가하는 부분 수열의 길이를 저장합니다. 그런 다음 dp의 모든 요소를 1로 초기화합니다.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}이 주어지면 dp 벡터는 다음과 같이 초기화됩니다.
dp[0] = 1
dp[1] = 1
dp[2] = 1
dp[3] = 1
dp[4] = 1
dp[5] = 1
다음으로 왼쪽에서 오른쪽으로 a의 요소를 반복합니다. 각 요소 a[i]에 대해 a[i] 앞의 모든 a 요소를 반복합니다. 각 요소 a[j]에 대해 a[j] < a[i]를 확인합니다. 그렇다면 dp[i]를 max(dp[i], dp[j] + 1)로 업데이트합니다. prev[i]도 j로 업데이트합니다.
예를 들어, 인덱스 2에서 값 20이 주어지면 a[0], a[1] 및 a[3]을 확인합니다. a[0]과 a[1]은 a[2]보다 작기 때문에 dp[2]를 max(dp[2], dp[0] + 1) 및 max(dp[2], dp[1] + 1)로 업데이트합니다. prev[2]를 0과 1로 업데이트합니다.
a의 모든 요소를 반복한 후 dp[n] 요소에는 가장 긴 증가하는 부분 수열의 길이가 저장됩니다. 그런 다음 prev를 사용하여 가장 긴 증가하는 부분 수열을 재구성할 수 있습니다.
예를 들어, dp[n]이 4이면 가장 긴 증가하는 부분 수열은 길이가 4인 수열입니다. prev를 사용하여 가장 긴 증가하는 부분 수열을 재구성할 수 있습니다. prev[n]은 가장 긴 증가하는 부분 수열의 마지막 요소의 인덱스입니다. prev[prev[n]]은 두 번째로 마지막 요소의 인덱스입니다. 이를 계속하면 가장 긴 증가하는 부분 수열의 모든 요소를 얻을 수 있습니다.
마지막으로 가장 긴 증가하는 부분 수열의 길이와 가장 긴 증가하는 부분 수열 자체를 출력합니다.
