[알고리즘] 백준 11053번: 가장 긴 증가하는 부분 수열 (C++), 첫 LIS

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

'가장 긴 증가하는 부분 수열(LIS)' 문제는 이분 탐색 공부할 때, 처음 존재를 알고, 그 뒤로 종종 어디선가 계속 보이길래 LIS라는 키워드가 유명한 건지 LIS라는 알고리즘이 따로 있는 건지 궁금했다. 그 뒤로 DP를 풀면서 정면으로 마주치게 되었다.

LIS(Longest Incresing Subsequence)는 말 그대로 주어진 수열 중 증가하는 부분 수열을 가져오는데 그중에 제일 긴 부분 수열을 구하는 문제다.

풀어보면서 느낀 거지만 LIS라는 알고리즘이 따로 있는 건 아니고, DP 문제 키워드 중 유명한 키워드에 속하는 거 같다.

 

+수열 vs 집합

간혹 사람들이 헷갈리는 거 같았다.

나도 정확히 '이건 뭐다'라고 정의할 수는 없지만

간단히 설명하면 수열은 '순서'가 있고, 집합은 순서를 신경 쓰지 않아도 되는 점이 차이점 같다.
(오피셜은 아니지만 지금까지 문제를 풀어보면서 그렇게 느꼈다.)

 

처음에 풀려고 시도할 때는 당연히 못 풀었다.

'DP인 거 같긴 한데 어떻게 풀지?'라는 생각밖에 안 들어서 솔루션을 참고했다.

(+참고 https://yabmoons.tistory.com/516)

 

1. 주어진 배열(전체 수열)만큼 메모이제이션을 할 배열을 만든다. <= 여기까지는 기본적인 DP를 풀 때

2. n번째 원소에서 1 ~ n - 1 원소 중에 n번째 원소보다 작으면서 그중에 메모이제이션 되어있는 길이 중 가장 큰 값을 찾는다.

(설명은 간단하게 되어있지만 처음 보는 사람들은 어렵게 느껴진다. DP의 개념 중 핵심인 작은 문제로부터 큰 문제까지 점진적으로 해결해나간다를 기억해내면 어려울 거 없다.)

2.5 왜 어렵게 느낄 거라고 생각했냐면 '1 ~ n - 1의 원소들에는 어떻게 메모이제이션이 되어있는 거지'라고 생각할 거 같기 때문이다.

 

TC를 가지고서 얘기해보자.

6
10 20 10 30 20 50

다음과 같은 TC가 있다.

n번째까지 가기 위해 1부터 시작한다.

1번째 원소 값은 10, 제일 첫 번째 원소이기 때문에 그 전의 원소는 존재하지 않는다.

>> 즉, 현재까지 제일 긴 부분 수열의 길이는 1이다. 1을 1번째 메모이제이션 배열에 저장한다.

 

2번째 원소 값은 20, 20 전에 10이라는 원소가 있다.

>> 10은 20보다 작으므로 현재까지 가장 작은 부분 수열의 길이는 2다. 2라는 값을 메모이제이션 배열에 저장한다.

 

3번째 원소 값은 10, 3번째 이전에는 10, 20이라는 수열이 있다.

하지만, 이 중에는 10보다 작은 값이 없으므로 10 그 자체만으로 3번째 원소에서 시작했을 때 가장 긴 부분 수열이 될 수 있다.

>> 1이 제일 긴 값이 되므로 메모이제이션 배열에 1을 넣어준다.

 

4번째 원소 값은 30, 4번째 이전에는 10, 20, 10이라는 수열이 있다.

3번째 ~ 4번째를 볼 때는 10, 30으로 가장 긴 부분 수열은 10, 30이 된다. 10(3번째 원소)까지 가장 긴 부분 수열의 길이가 1이었으므로 거기다가 30이 추가되기 때문에 +1을 하여 2가 된다.

2번째 ~ 4번째를 볼 때는 20, 10, 30으로 가장 긴 부분 수열은 20, 30 혹은 10, 30이 될 것이다.

하지만, 20(2번째 원소)에서 가장 긴 부분 수열의 길이 값은 2였다. 즉, 20을 고르면 더 긴 부분 수열이 될 수 있다는 뜻이다. 10, 20, 10, 30이 채택된다는 소리다.

1번째 ~ 4번째는 3번째 ~ 4번째와 같은 경우로 PASS

>> 20이 제일 긴 부분 수열 값(2)을 가지고 있으므로 +1을 하여 메모이제이션 배열 4번째 인덱스에 3을 저장한다.

 

모든 경우의 수를 다루었으므로

6
10 20 10 30 20 50
1   2   1   3   2   4

다음과 같은 3번째 줄 값들이 각각의 메모이제이션 배열 인덱스 값에 담기는 것을 알 수 있다.

---

솔루션

위의 내용을 코드로 표현해보자.

(+참고 https://yabmoons.tistory.com/516)

#include <iostream>
#include <algorithm>
using namespace std;

int n;
int arr[1001];
int cache[1001];

int main() {
	cin >> n;
	int value;
	for (int i = 1; i <= n; i++) {
		cin >> value;
		arr[i] = value;
	}

	for (int i = 1; i <= n; i++) {
    // 점진적으로 해결해나간다는 것을 생각하라.
    // 작은 문제(1)부터 큰 문제(n)까지
		cache[i] = 1; // 자체만으로 가장 긴 부분 수열이 되는 경우
		for (int j = i - 1; j >= 1; j--) { // n번째 수 >> 1 ~ n - 1의 수들 고려
			if (arr[i] > arr[j]) { // 증가하는 수열이기 때문에 n번째 수보다 작아야 함
				cache[i] = max(cache[i], cache[j] + 1); // 
			}
		}
	}

	// 무작정 n번째 cache 뽑으면 안 됨
    // 제일 큰 값을 뽑아야 함
    // 굳이 정렬 안 써도 됨
    // 이해를 돕기 위해 최대한 점화식을 안 건드려 했어서 정렬을 사용함
    // cache[i]를 즉각적으로 최댓값을 구하는 게 코드 시간에도 좋다.
	sort(cache, cache + n + 1);

	cout << cache[n];
	return 0;
}

---

백준에는 LIS 관련된 문제들이 꽤나 있다. 그래도 한 번 이해하면 다른 문제들은 보다 이해하기 쉽다.