문제 링크:
가장 긴 증가하는 부분 수열: https://www.acmicpc.net/problem/11053
가장 긴 감소하는 부분 수열: https://www.acmicpc.net/problem/11722

Thumbnail: Photo by Denys Sudilkovsky (Unsplash)

LIS 유형을 공부하면서, 시리즈를 좀 풀어보려고 합니다. 가장 쉬운 두 문제를 풀어봤습니다.

풀이

LIS 이해하기

LIS(Longest Increase Subsequence, 가장 긴 증가하는 부분 수열)은 전체 수열의 부분 수열 중에서, "증가하는" 부분 수열 중 가장 길이가 긴 것을 찾는 유형입니다. DP와 이분탐색으로 풀 수 있습니다. 이 문제는 DP를 활용해서 풀었습니다.

DP로 풀기

먼저, 원본 수열을 다음과 같이 배열로 나타냅니다.

이제, arr[i]를 끝 원소로 가지는 부분 수열의 최대 길이를 dp 배열에 저장해보겠습니다.

dp = [1 for _ in range(N)]
for i in range(N):
    for j in range(i + 1, N):
        if A[j] > A[i]:
            dp[j] = max(dp[j], dp[i] + 1)

\(O(N^2)\) 의 시간 복잡도로 LIS를 구할 수 있습니다. 다만, 시간 복잡도로 인해 입력 받는 수열의 길이가 크다면 시간 초과가 발생할 수 있으니, 문제 조건을 미리 확인해 DP로 풀 수 있는지 확인해야 합니다.

가장 긴 감소하는 부분 수열

앞서 본 내용은 '가장 긴 증가하는 부분 수열'에 대한 DP 풀이이며, 이는 BOJ 11053의 풀이이기도 합니다.

동일한 풀이를 사용할 수 있는 다른 문제인 '가장 긴 감소하는 부분 수열' (BOJ 11722)에 대한 풀이도 간단히 정리하겠습니다.

앞서 dp배열을 계산할 때, '가장 긴 증가하는' 이라는 조건을 위해 배열의 두 원소를 비교할 때 다음 원소(j)가 기준값(i)보다 큰지 비교했다면, '가장 긴 감소하는' 이라는 조건을 위해서는 반대로 j가 i보다 작은지 비교하면 됩니다.

dp = [1 for _ in range(N)]
for i in range(N):
    for j in range(i + 1, N):
        if A[j] < A[i]:
            dp[j] = max(dp[j], dp[i] + 1)

전체 코드

BOJ 11053

input = open(0).readline
N = int(input().strip())
A = list(map(int, input().strip().split()))

dp = [1 for _ in range(N)]
for i in range(N):
    for j in range(i + 1, N):
        if A[j] > A[i]:
            dp[j] = max(dp[j], dp[i] + 1)

print(max(dp))

BOJ 11722

input = open(0).readline
N = int(input().strip())
A = list(map(int, input().strip().split()))

dp = [1 for _ in range(N)]
for i in range(N):
    for j in range(i + 1, N):
        if A[j] < A[i]:
            dp[j] = max(dp[j], dp[i] + 1)

print(max(dp))