수열이 주어졌을 때, 가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence)을 DP(Dynamic Programming, 동적 계획법)를 이용해 풀이하는 방법을 설명한다.
아이디어
각 원소를 끝으로 하는 증가하는 부분 수열의 최대 길이를 저장하는 방식으로 풀 수 있다.
즉, i번째 수를 마지막으로 하는 증가 수열 중 최대 길이를 dp[i] 에 저장한다. 이는 곧 우리가 구하고자 하는 값은 dp 배열의 최댓값(max)가 된다.
코드를 먼저 제시하고 이를 기반으로 설명하는게 낫다고 생각한다. 정답 코드는 다음과 같다.
코드
n = int(input())
arr = list(map(int,input().split()))
dp = [1 for _ in range(n)]
for i in range(1, len(arr)):
for j in range(0, i):
if arr[i] > arr[j]:
dp[i] = max(dp[i], dp[j]+1)
print(max(dp))이중 for문을 사용한 이유
일반적인 DP 문제(피보나치, 계단 오르기, 최소 비용 경로 등)는 대부분 연속적인 상태 간의 관계를 가진다. 따라서 dp[i] 는 dp[i-1], dp[i-2] 처럼 고정된 앞의 값들만 참조하면 된다.
그러나, LIS 는 그렇지 않다. 연속적인 수열이 아닌, 증가하는 부분 수열을 찾는 문제이기 때문이다.
LIS 는 연속되지 않으므로(Subsequence), 앞의 모든 경우를 고려해야 한다.
dp[i]는 i번째 원소를 마지막으로 하는 LIS 의 최대 길이이다.- 어떤 인덱스 j (0 <= j < i) 에서
arr[j] < arr[i]인 경우에만 연결이 가능하므로 dp[i]계산할 때는 모든 이전 인덱스 j 들을 전부 탐색해야 한다.
즉, 앞의 값 중 어떤 것이 이어질 수 있을지 모르기 때문에, 가능한 값(dp[j])들 중 가장 큰 값을 찾아야 한다. 이를 위해선 모든 경우를 살펴보는 이중 for 문이 필수이다.
예시를 들어 이중 for 문이 필요한 이유를 자세히 살펴보자.
수열 10 20 10 30 20 50이 있다고 하자.
이때 현재 위치한 인덱스(i)에서, 자신의 앞에 있는 인덱스(0 <= j < i)들을 순회하며 조건부(arr[i] > arr[j]) 인 값들에 대해 dp[i] = max(dp[i], dp[j]+1)을 해줘야 한다. 배열이 연속적으로 증가하는 것이 아니기 때문에 j1 < j2 < i 일때 dp[j1] < dp[j2] 가 항상 성립하는 것이 아니기 때문이다. (실제로 위 수열에서 dp[3] 은 dp[4] 보다 크다)
따라서 위 과정을 거치면, 내부 i가 5일때, 내부 for 문에서 j가 3일때 dp[5] = max(3, dp[3]+1) 을 거쳐서 4를 갖게 되고, j 가 4일때 dp[5] = max(4, dp[4]+1)일때 그대로 4를 갖게 된다.
마지막으로 우리가 구하고자 하는, 주어진 수열 내에서 가장 긴 증가하는 부분 수열의 길이(LIS)는 max(dp) 이다.
(추가) 실제 LIS 구하기
위에서 LIS 의 길이를 구하였지만, 우리는 가능한 LIS 들 중에서 하나를 찾고 싶을 수도 있다(길이가 같은 LIS 는 여러 개 존재할 수 있다). 이 경우 위 방법에서 DP의 직전 경로를 기록하는 방법을 추가하면 된다.
주요 특징은 바깥 반복문에서 i 가 가능한 최대의 dp[j]+1 를 가질 때의 j 를 이전 경로(인덱스)로 가지도록 한다, 그러나 기존이랑 조금 다른 점이 있는데, 기존 dp 방식 LIS 길이 계산에서는
for i in range(1, len(arr)):
for j in range(0, i):
if arr[i] > arr[j]:
dp[i] = max(dp[i], dp[j] + 1)위와 같이 작성하였지만, 이 경우에는 dp[j]+1 이 큰지, dp[i] 가 큰지 명시적으로 알 수 없다. 따라서 아래와 같이 추가적인 코드를 작성하게 된다.
for i in range(1, len(arr)):
for j in range(0, i):
if arr[i] > arr[j]:
dp[i] = max(dp[i], dp[j] + 1)
if dp[j] + 1 > dp[i]:
prev[i] = j이를 최적화하기 위해 애초에 조건문에서부터 dp[j] + 1 이 dp[i] 보다 더 큰지 검증하는 과정을 거치도록 한다.
for i in range(1, len(arr)):
for j in range(0, i):
if arr[i] > arr[j] and dp[j] + 1 > dp[i]: # 이렇게!
dp[i] = dp[j] + 1
prev[i] = j이때의 i, j 는 실제 LIS 의 조건을 만족하기 때문에 전체 DP 계산 후, 제일 큰 값을 가지는 DP 의 인덱스로부터 prev 를 우리가 구한 LIS 의 길이(max(dp)만큼 반복하여 따라가면 된다.
따라가면서 (LIS 가 될) 결괏값 배열에 append() 를 해준 다음, 뒤집어서 출력하면 된다.
코드
import sys
input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
dp = [1 for _ in range(len(arr))] # dp = [1] * n
prev = [-1 for _ in range(len(arr))] # dp [-1] * n
for i in range(1, len(arr)):
for j in range(0, i):
if arr[i] > arr[j] and dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
prev[i] = j # 역 추적 경로 저장
# 최댓값 및 그 인덱스 찾기
max_len = max(dp)
max_idx = dp.index(max_len) # 가장 마지막에 올 수 있는 값(들 중 하나)의 인덱스
# 실제 LIS 구하기
cur_idx = max_idx
ans = []
for _ in range(max_len):
ans.append(arr[cur_idx])
cur_idx = prev[cur_idx]
print(max_len)
print(' '.join(map(str, reversed(ans))))