[자료구조/알고리즘] 최장 증가 부분 수열 (LIS, Longest Increasing Subsequence)

Posted Nov 27, 2025 Updated Dec 30, 2025

By FickleBoBo

9 min read

1. LIS

LIS는 Longest Increasing Subsequence의 약자로 최장 증가 부분 수열을 의미한다. 컴퓨터 공학에서 LIS 문제는 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 찾는 문제로 여기서의 부분 수열은 연속적이거나 유일할 필요는 없다. LIS는 DP 문제로 전체 수열의 LIS를 더 작은 부분 수열의 LIS를 통해 구해나가며 기존 계산한 LIS 값들을 활용한다.

2. 2중 반복문을 활용한 LIS

주어진 수열이 $\{10, 45, 30, 35, 20, 25, 40, 15\}$ 일 때 2중 반복문을 활용하면 간단하게 LIS를 구할 수 있다.

먼저 주어진 수열과 같은 크기의 dp 배열을 선언해준다. dp 배열은 해당 원소를 포함하는(끝 값으로 갖는) LIS의 길이를 갖는다.

첫 번째 원소인 $10$ 을 포함하는 LIS의 길이는 $1$ 이므로 해당 dp 배열의 값은 $1$ 이 된다.

두 번째 원소인 $45$ 를 포함하는 LIS의 길이는 해당 원소 이전까지의 원소들 중 해당 원소보다 작은 원소들의 LIS에서 해당 원소를 뒤에 더하면 LIS가 되므로 해당 dp 배열의 값은 $2$ 이 된다. ($10$ 뒤에 $45$)

세 번째 원소인 $30$ 을 포함하는 LIS의 길이는 해당 원소 이전까지의 원소들 중 해당 원소보다 작은 원소들의 LIS에서 해당 원소를 뒤에 더하면 LIS가 되므로 해당 dp 배열의 값은 $2$ 이 된다. ($10$ 뒤에 $30$)

네 번째 원소인 $35$ 를 포함하는 LIS의 길이는 해당 원소 이전까지의 원소들 중 해당 원소보다 작은 원소들의 LIS에서 해당 원소를 뒤에 더하면 LIS가 되므로 해당 dp 배열의 값은 $3$ 이 된다. ($30$ 뒤에 $35$)

$10$ 과 $30$ 모두 $35$ 보다 작은데 이때는 더 긴 LIS를 선택하면 된다.

다섯 번째 원소인 $20$ 을 포함하는 LIS의 길이는 해당 원소 이전까지의 원소들 중 해당 원소보다 작은 원소들의 LIS에서 해당 원소를 뒤에 더하면 LIS가 되므로 해당 dp 배열의 값은 $2$ 이 된다. ($10$ 뒤에 $20$)

여섯 번째 원소인 $25$ 를 포함하는 LIS의 길이는 해당 원소 이전까지의 원소들 중 해당 원소보다 작은 원소들의 LIS에서 해당 원소를 뒤에 더하면 LIS가 되므로 해당 dp 배열의 값은 $3$ 이 된다. ($20$ 뒤에 $25$)

일곱 번째 원소인 $40$ 을 포함하는 LIS의 길이는 해당 원소 이전까지의 원소들 중 해당 원소보다 작은 원소들의 LIS에서 해당 원소를 뒤에 더하면 LIS가 되므로 해당 dp 배열의 값은 $4$ 이 된다. ($35$ 뒤에 $40$ 또는 $25$ 뒤에 $40$)

마지막 원소인 $15$ 를 포함하는 LIS의 길이는 해당 원소 이전까지의 원소들 중 해당 원소보다 작은 원소들의 LIS에서 해당 원소를 뒤에 더하면 LIS가 되므로 해당 dp 배열의 값은 $2$ 이 된다. ($10$ 뒤에 $15$)

이렇게 각 원소를 포함하는 LIS의 길이를 dp 배열에 모두 구할 수 있다. dp 배열의 최댓값인 $4$ 가 해당 수열의 LIS가 되며 각 원소에 대한 순회와 각 원소의 앞 원소 중 LIS 후보를 찾는 과정때문에 $O(N^2)$ 의 시간복잡도와 dp 배열을 위한 $O(N)$ 의 공간복잡도가 소요된다.

2중 반복문을 활용한 LIS에서 dp 배열의 초기값은 자기 자신만으로 LIS가 가능하므로 $1$ 이 되며 점화식은 아래와 같다.

\[dp[i] = \max_{\substack{0 \le j < i \\ A[j] < A[i]}} \left( dp[j] + 1 \right)\]

2중 반복문을 활용한 LIS는 수열의 길이가 $N$ 일 때, $O(N^2)$ 의 시간복잡도와 $O(N)$ 의 공간복잡도가 소요되는 알고리즘이다.

3. 역추적을 통한 실제 LIS 구하기

위 과정을 통해 주어진 수열의 LIS의 길이를 구할 수 있었는데 LIS의 길이 뿐만 아니라 실제 LIS도 구할 수 있다. 실제 LIS를 구하기 위해 $prev$ 라는 임시 배열을 활용하는데 이 $prev$ 에는 dp 배열에 LIS의 갱신을 발생시켰던 원소의 인덱스를 저장한다. 인덱스는 $0$ 이상의 정수이기 때문에 이전의 어떤 원소도 LIS의 갱신을 발생시키지 않았음을 표현하기 위해 초기에는 $-1$ 같은 음수로 초기화하면 된다.

위 수열에 대해 $prev$ 배열을 구하면 아래와 같다.

dp 배열에서 최댓값이 위치한 곳이 LIS의 끝 원소이므로 해당 위치부터 $prev$ 배열을 통해 역순으로 LIS를 구할 수 있다. dp 배열의 최댓값이 $4$ 이므로, LIS를 탐색할 초기 위치는 아래와 같다. 표시한 곳과 동일한 인덱스인 $40$ 이 실제 LIS의 마지막 원소가 된다.