문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

풀이

최장증가수열(LIS, Longest Increasing Subsequence)알고리즘을 쓰는 기초적인 문제다. 이전에 백준 2565 전깃줄문제를 접했다가 LIS알고리즘이 필요한 문제인 것을 깨닫고 해당 문제부터 풀어보려고 한다.

dp(dynamic programming)방식을 사용하면 간단하다.
dp라는 리스트를 하나 만들어 각 인덱스까지의 만들수 있는 최장증가수열의 길이를 저장한다. dp[5]는 입력받은 수열의 5번째까지 수를 이용하여 만들 수 있는 최장증가수열의 길이를 의미한다.

코드

import sys

n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
dp = [1] * len(arr)

for i in range(len(arr)):
    for j in range(i):
        if arr[j] < arr[i]:  # i번째값이 j번째값보다 크다면 최장증가수열의 길이가 증가할 가능성 있음
            # 1. i번째 값을 추가함으로서, 더 긴 최장증가수열을 만들 수 있는 경우
            # 2. j번째 값을 이용해 수열을 구하는 경우보다 더 긴 수열을 만들 수 있는 경우가 존재
            dp[i] = max(dp[j]+1, dp[i]) 
print(max(dp))

이중반복문을 통해 비교하면서 dp를 갱신해주면 된다.
갱신되는 타이밍이 arr[j] < arr[i]에서, dp[i] = max(dp[j]+1, dp[i])로 갱신해준다.

1. dp[j]+1로 갱신되는 경우는, 기존에 계산된 최장증가수열의 길이에 arr[i]가 추가되면서 길이가 1증가하는 경우이다.
2. dp[i]로 유지되는 경우는, arr[j]를 사용하여 최장증가수열을 만드는 것보다, 이미 더 긴 최장증가수열을 만들 수 있는 경우가 존재한다.

2번째 경우는 아래 그림과 같다.

위 코드 기준으로 i=5, j=4일 때, 현재 dp[5]=3 이다. arr[j] < arr[i]이긴 하지만 max(dp[j]+1, dp[i]) = max(2,3) = 3이다. 1을 포함하여 최장증가수열을 구성하는 것보다 더 긴 최장증가수열의 길이가 이미 계산되었음을 의미한다. [1,5]보다는 [2,4,5]가 더 길다.

위 코드는 제일 간단한 방법으로 구현한 것이다. 시간복잡도가 $O(n^2)$이기 때문에, 입력받는 수열의 길이가 커지면 시간이 매우 오래 걸릴것이다. 또한 최장증가수열를 직접 구할 수 없으니 다른 LIS문제를 풀면서 고민해봐야겠다.