최장 증가 부분 수열 (LIS)

• LIS: Longest Increasing Subsequence
• 방법
  • $O(N^2)$
  • $O(NlogN)$ - Binary Search 활용
• 더 많은 문제 목록

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

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

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

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

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

문제 예시

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

public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int N = Integer.parseInt(br.readLine());

	int[] dp = new int[N];
	int[] A = Arrays.stream(br.readLine().split(" "))
                    .mapToInt(Integer::parseInt).toArray();

	int m = 1;
	for (int i = 0; i < N; i++) {
		dp[i] = 1;
		for (int j = 0; j < i; j++) {
			if (A[j] >= A[i]) continue;
			if (dp[j] + 1 <= dp[i]) continue;
			dp[i] = dp[j] + 1;
			m = m < dp[i] ? dp[i] : m;
		}
	}
	System.out.println(m);
}

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

$O(NlogN)$ - Binary Search 활용

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

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

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

문제 예시

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

public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

	int N = Integer.parseInt(br.readLine());
	int[] A = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

	ArrayList<Integer> LIS = new ArrayList<Integer>();
	// 처음 나온 수는 바로 저장.
	LIS.add(A[0]);

	for (int i = 1; i < N; i++) {
		int a = A[i];

		// 길이가 0 이상이면
		// 마지막에 나온 수랑 비교해서
		int last = LIS.get(LIS.size() - 1);
		if (a > last) {
			// 이번 수가 마지막 수보다 크면 부분 수열에 추가
			LIS.add(a);
		} else {
			// 이번 수가 마지막 수보다 작다면 LIS 배열 내 어떤 수와 대치
			int idx = Collections.binarySearch(LIS, a);

			// binarySearch 함수는 만약 같은 수가 있다면 인덱스를 반환하고
			// 같은 수가 없다면 키보다 큰 값 중 첫 번째 값의 인덱스를 음수로 반환
			idx = idx >= 0 ? idx : -(idx + 1);

			// 그 위치의 수와 대치
			LIS.set(idx, a);
		}
	}
	// 결과 출력
	System.out.println(LIS.size());
}

더 많은 문제 목록

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

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

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

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