최장 증가 부분 수열 (LIS)

LIS: Longest Increasing Subsequence

최장 증가 부분 수열이란, 주어진 수열의 원소 일부로 구성된 부분 수열 중 원소가 오름차순으로 정렬된 가장 긴 부분 수열입니다¹. 만약 주어진 수열이 8 2 4 3 6 11 7 10 14 5라면 이 수열의 LIS는 2 4 6 7 10 14가 될 수 있습니다. 이 떄, 길이가 가장 긴 부분 수열은 하나가 아닐 수 있습니다. 위 예시에서 2 3 6 7 10 14 또한 길이는 6으로 동일하고 오름차순 정렬된 성질을 만족합니다.

방법

LIS의 길이를 구하는 방법은 크게 두 가지가 있습니다.

$O(N^2)$

첫 번째 방법은 DP를 활용한 방법입니다. LIS[] 배열이 있다고 생각하고 수열의 수를 하나씩 확인하면서 이번 숫자가

• 이전 LIS 배열의 어떤 숫자보다 작으면 오름차순의 성질을 만족하지 못하므로 넘어갑니다.
• 어떤 숫자보다 크다면 그 수까지로 만들 수 있는 LIS 배열 길이 + 1이 이번 숫자까지 만들 수 있는 LIS 배열의 길이가 됩니다.

$\text{for } i \text{ in } 1 → N \$ $\quad LIS[i] = 1 \quad\quad\quad\quad\quad\quad\quad\text{// 최소 길이는 이 수 하나만 있는 수열} \$ $\quad \text{for } j \text{ in } 1 → i - 1 \$ $\quad\quad \text{if } a_j \lt a_i \text{ and } LIS[i] \lt LIS[j] + 1 \$ $\quad\quad\quad LIS[i] = LIS[j] + 1 \$ $\text{return max}(LIS[])$

실제 예시로 보자면 주어진 수열이 3 2 6 4 5 1인 경우

1. 3은 처음 나왔으므로 LIS[0] = 1
2. 2는 자신 앞에 자신보다 작은 수가 없으므로 LIS[1] = 1
3. 6은 자신 앞에 3, 2가 있는데 둘 다 1이므로 LIS[2] = LIS[1] + 1 = 2
4. 4는 6과 같이 자신 앞에 자신보다 작은 수가 3, 2가 있는데 둘 다 1이므로 LIS[3] = LIS[1] + 1 = 2
5. 5는 3, 2, 4가 있는데 그 중 LIS[] 값이 가장 큰 LIS[3] = 2 뒤에 붙어야 LIS의 길이가 가장 커지므로 LIS[4] = LIS[3] + 1 = 3
6. 1은 자신 앞에 자신보다 작은 수가 없으므로 LIS[5] = 1

이렇게 수행하면 다음과 같은 결과를 얻을 수 있습니다.

1idx:      0 1 2 3 4 5
2original: 3 2 6 4 5 1
3LIS:      1 1 2 2 3 1

이때 주의해야 할 점으로 LIS 배열에 채워진 마지막 값 LIS[-1] = 1이 답이 아니라는 것입니다. LIS의 길이를 알고 싶다면 LIS 배열에서 가장 큰 값을 다시 찾아줘야 합니다.

이 방법으로는 매 숫자마다 자기 자신 전의 모든 수를 다 훑어봐야 하므로 결과적으로 시간복잡도는 $O(N^2)$로 나타낼 수 있습니다.

문제 예시

다음 Java 코드는 위에서 설명한 알고리즘을 구현하여 백준 11053 가장 긴 증가하는 부분 수열 문제를 해결한 예시입니다.

 1public static void main(String[] args) throws IOException {
 2	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 3	int N = Integer.parseInt(br.readLine());
 4
 5	int[] dp = new int[N];
 6	int[] A = Arrays.stream(br.readLine().split(" "))
 7                    .mapToInt(Integer::parseInt).toArray();
 8
 9	int m = 1;
10	for (int i = 0; i < N; i++) {
11		dp[i] = 1;
12		for (int j = 0; j < i; j++) {
13			if (A[j] >= A[i]) continue;
14			if (dp[j] + 1 <= dp[i]) continue;
15			dp[i] = dp[j] + 1;
16			m = m < dp[i] ? dp[i] : m;
17		}
18	}
19	System.out.println(m);
20}

그러나 $O(N^2)$는 입력 크기 $N$이 조금만 커져도 시간적으로 문제가 되는 단점이 있습니다. 그러면 이 문제를 어떻게 해결할 수 있을까요?

$O(NlogN)$ - Binary Search 활용

앞서 설명한 알고리즘의 시간 복잡도가 $O(N^2)$라고 했는데, 일단 원본 수열에 포함된 모든 수를 한 번씩은 확인해야 하므로 $N$은 뺄 수 없습니다. 그러면 문제는 ‘자기 자신보다 앞서는 모든 수를 다 훑어보는 과정’에서 $N$이 추가되는 것입니다.

이번 숫자를 끼워 넣을 자리 인덱스를 찾을 때 선형 탐색이 아닌 이분 탐색을 하면 어떨까요? 그러면 탐색에 걸리는 시간을 $\log{N}$으로 줄일 수 있을 것입니다. 이번 숫자를 끼워넣을 자리는 이미 동일한 숫자가 있으면 해당 인덱스를, 동일한 숫자가 없다면 이번 숫자보다 큰 수 중 가장 작은 수가 저장된 위치를 사용합니다.

주의해야 할 점으로 이 방법은 부분 수열 자체를 구하는게 아니라 최장 증가 부분 수열의 **길이**를 빠르게 구하는 알고리즘입니다. 부분 수열 자체를 구하지 못하는 것은 아니지만, 로직에 약간의 수정이 필요합니다.

문제 예시

다음 Java 코드는 위에서 설명한 알고리즘을 구현하여 백준 12015 가장 긴 증가하는 부분 수열 2 문제를 해결한 예시입니다.

 1public static void main(String[] args) throws IOException {
 2	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 3
 4	int N = Integer.parseInt(br.readLine());
 5	int[] A = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
 6
 7	ArrayList<Integer> LIS = new ArrayList<Integer>();
 8	// 처음 나온 수는 바로 저장.
 9	LIS.add(A[0]);
10
11	for (int i = 1; i < N; i++) {
12		int a = A[i];
13
14		// 길이가 0 이상이면
15		// 마지막에 나온 수랑 비교해서
16		int last = LIS.get(LIS.size() - 1);
17		if (a > last) {
18			// 이번 수가 마지막 수보다 크면 부분 수열에 추가
19			LIS.add(a);
20		} else {
21			// 이번 수가 마지막 수보다 작다면 LIS 배열 내 어떤 수와 대치
22			int idx = Collections.binarySearch(LIS, a);
23
24			// binarySearch 함수는 만약 같은 수가 있다면 인덱스를 반환하고
25			// 같은 수가 없다면 키보다 큰 값 중 첫 번째 값의 인덱스를 음수로 반환
26			idx = idx >= 0 ? idx : -(idx + 1);
27
28			// 그 위치의 수와 대치
29			LIS.set(idx, a);
30		}
31	}
32	// 결과 출력
33	System.out.println(LIS.size());
34}

더 많은 문제 목록

LIS 문제는 방법이 여러 개 있고 이들의 시간 복잡도가 다르기 때문에 입력 크기 N을 조절해 난이도를 바꾸기 좋은 유형입니다. 따라서 여러 문제를 풀어보며 연습하는 것이 좋습니다.

• 백준 가장 긴 증가하는 부분 수열 문제 목록

Prerequisites: 이 글에서 언급되었으나 깊게 설명하지 않은 내용입니다.

• DP (Dynamic Programming, 동적 계획법)