[JAVA] 최장 증가 수열 (LIS)

최장 증가 수열 : Longest Increasing Subsequence

 

📌 최장 증가 수열이란?

어떤 배열이 있을 때, 배열의 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분수열을 추출한 것입니다.

 

예를들어,

[4, 2, 3, 1, 5, 6]이라는 배열이 있을 때 LIS는 [2, 3, 5, 6]이 됩니다.

점차 증가하는 배열은 [4, 5, 6] 또는 [2, 3, 5, 6] , [3, 5, 6] 등 여러 부분집합이 있을 수 있지만,

그 중 부분집합의 최대 배열을 의미하므로 LIS는 [2, 3, 5, 6]이 됩니다.

 

🔍 가장 먼저 생각해 볼 수 있는 풀이는 완전탐색(Brute-Force)입니다.

수열의 모든 부분 집합을 구하여 그 부분 집합이 증가 수열인지를 판단합니다.

완전탐색으로 풀 경우 부분 수열의 길이가 긴 것부터 조사하여 백트래킹을 이용하는 방법이 있습니다.

부분집합 알고리즘을 활용할 경우, O(2^n)의 시간 복잡도를 가지므로 효율적이라고는 할 수 없습니다.

 

 

🔍따라서 DP(Dynamic Programming)를 통한 접근 방식을 생각합니다.

LIS배열을 만들어서 최장 부분 수열의 길이를 저장합니다.

LIS(i)가 a[i]를 포함하고 있을때와, 포함하고 있지 않을 때를 비교하는 점화식을 세웁니다.

 

아래에서 LIS[i]는 원소i가 수열의 마지막일 때 최장길이 값을 의미합니다.

int max = 0;  //해당 수열의 LIS 최장길이
for (int i = 0; i < N; i++) {  //모든 원소에 대해 자신을 끝으로 하는 LIS길이 계산
	LIS[i] = 1; //자신 혼자 LIS 구성할 때의 길이 1로 초기화
	for (int j = 0; j < i; j++) {  //첫 원소부터 i원소 직전까지 비교
		if (arr[j] < arr[i] && LIS[i] < LIS[j] + 1) {  //arr[j]<arr[i] : 증가수열의 모습
			LIS[i] = LIS[j] + 1;
		}
	}
	if (max < LIS[i]) max = LIS[i];
}

먼저 해당 수열의 LIS 최장길이를 저장할 max변수를 선언합니다.

다음으로 주어진 배열의 길이만큼 입력 배열을 탐색합니다.

자신 혼자 LIS를 구성할 때의 길이는 1로 초기화 한 뒤,

첫 원소부터 현재 탐색하고 있는 i번째 원소 직전까지 비교합니다. 

만약 j번째 원소가 i번째 원소보다 작다면, 증가 수열의 모습을 띄고있으므로 LIS[i]에 현재 경우 1을 더합니다.

만약 j번째 원소가 i번째 원소보다 크거나 같다면, LIS[i]는 추가하지 않고 진행합니다.

원소를 하나씩 탐색할 때 마다 더 큰 값으로 max값을 갱신해줍니다.