LIS

LIS

LIS; Longest Increasing Subsequence

최장 증가 부분 수열

original array의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열

 

---

 

LIS 길이 구하기

1. DP - O(N^2)

length를 아래와 같이 정의할 때, DP를 활용하여 LIS의 길이를 구할 수 있다.

length[i]: i번째 인덱스에서 끝나는 최장 증가 부분 수열의 길이

이때 length.size == array.size 이다.

for (i in array.indices) {
	length[i] = 1
	for (j in 0 until i) {
		if (array[j] < array[i]) length[i] = max(length[i], length[j] + 1)
	}
}

배열에서 idx를 하나씩 늘려가면서 내부 반복문으로 0~idx까지의 원소를 확인한다.

array[j] < array[i] 일 경우, length[i]를 업데이트한다.

1. 기존의 length[i]
2. j번째 인덱스에서 끝나는 최장 증가 부분 수열(length[j])마지막에 array[i]를 추가했을 때의 LIS 길이

위의 방법은 O(N^2)으로, 시간이 오래 걸린다. 이분탐색 알고리즘을 활용하여 시간을 줄이는 방식이 존재한다.

 

---

 

2. DP + BinarySearch - O(NLogN)

LIS를 불완전하게 저장하면서 이분탐색 알고리즘을 활용하여 시간복잡도를 개선한 방식이 존재한다.

var LIS = IntArray(10)
	
// LIS의 시작 인덱스와 끝 인덱스, num을 받아 LIS 내부에서 num이 위치해야 하는 idx값을 리턴하는 함수
fun binarySearch(start: Int, end: Int, num: Int): Int {
	var s = start
	var e = end

	while (s < e) {
		var mid = (s + e) / 2
		if (LIS[mid] < num) {
			s = mid + 1
		} else
			e = mid
	}

	return e
}

// LIS의 idx는 따로 사용한다
// LIS의 첫번째 원소는 array의 첫번째 원소로 초기화시킨다.
var idx = 0
LIS[0] = array[0]

for (i in array.indices) {
	if(LIS[idx] < array[i])
		LIS[++idx] = array[i]
	else
		LIS[binarySearch(0, idx, array[i])] = array[i]
}

배열의 인덱스를 차례로 증가시키며, 해당 인덱스의 원소가 LIS의 몇 번째 인덱스에 들어갈 수 있는지 이분탐색으로 탐색한다.

매 반복문마다 LIS의 마지막 원소와 현재 array의 원소를 비교한다.

1. 현재 array의 원소가 클 경우 LIS에 덧붙인다.
2. LIS의 마지막 원소가 클 경우 현재 array의 원소가 기존에 저장된 LIS의 내부에서 어디에 위치할 수 있는지 이분탐색하여 해당 인덱스에 현재 array의 원소를 저장한다.

외부반복문 O(N), 내부반복문 O(logN)으로 총 O(NlogN)으로 위의 DP 방식보다 훨씬 개선된 시간복잡도를 보인다.

❓ 왜 불완전한가?
위의 코드에서 LIS 는 LIS의 길이를 구하기 위한 DP 배열을 의미하는 것으로, 정확한 최종 LIS를 담고 있지 않다는 점을 유의하자. 
해당 알고리즘으로 정확성을 보장할 수 있는 정보는 길이뿐이다.

 

---

 

동작 방식 들여다보기

아래의 표는 {1, 6, 4, 5, 2, 3, 4, 5}에서 LIS의 길이를 구하기 위해 위 코드의 동작을 순서대로 나타낸 것이다.

idx/num	1	6	4	5	2	3	4	5
0	1
1	1	6
2	1	4
3	1	4	5
4	1	2	5
5	1	2	3
6	1	2	3	4
7	1	2	3	4	5

• idx = 2: 마지막 LIS의 원소인 6보다 현재 array의 원소인 4가 더 작으므로 이분탐색을 실행한다.
  • 이분탐색 결과 LIS[1] = 4
• idx = 3: 마지막 LIS의 원소인 4보다 현재 array의 원소인 5가 더 크므로 LIS의 뒤에 덧붙인다.
• idx = 4: 현재 array의 원소인 2의 위치를 이분탐색한다.
  • 이분탐색 결과 LIS[1] = 2

❗ LIS[1]이 덮어씌워졌어요. 이래도 되나요?

idx = 4까지의 original array는 {1, 6, 4, 5, 2}로, 최종 LIS는 {1, 4, 5}이다.

그러나 실제로 idx = 4에서의 LIS 를 출력해 보면 {1, 2, 5}가 저장되어 있다.

즉, 이 알고리즘은 각 idx마다 LIS의 길이를 정확하게 저장하지만, 다음에 들어올 원소를 위해 불완전하게 LIS를 저장한다.

 

---

 

실제 LIS 저장하기

실제 LIS를 알고 싶을 경우, array[i]가 LIS의 몇 번째 idx에 저장되는지 따로 기록해야 한다.

위 코드를 조금 수정하여 record라는 IntArray에 LIS 업데이트 정보를 기록해 보자.

fun binarySearch(start: Int, end: Int, num: Int): Int {
	var s = start
	var e = end

	while (s < e) {
		var mid = (s + e) / 2
		if (LIS[mid] < num) {
			s = mid + 1
		} else
			e = mid
	}
	return e
}

var idx = 0
LIS[0] = array[0]

// 여기가 추가되었어요
var record = IntArray(8)

for (i in array.indices) {
	if (LIS[idx] < array[i]) {
		LIS[++idx] = array[i]
		// 여기가 추가되었어요
		record[idx] = i
	} else {
		var bsIdx = binarySearch(0, idx, array[i])
		LIS[bsIdx] = array[i]
		// 여기가 추가되었어요
		record[bsIdx] = i
	}
}

record[i]에는 LIS에 업데이트된 array 원소의 idx값을 저장하게 되었다.

즉, LIS에서의 array[i]의 위치 정보를 알게 된 것이다.

{1, 6, 4, 5, 2, 3, 4, 5}에서 위 코드를 실행시켜 record를 저장해 보면 다음과 같이 저장된다.

0 4 5 6 7 0 0 0

 

최종적으로 LIS를 출력하려면 다음과 같이 0부터 idx까지 for문을 실행해 주면 된다.

for (i in 0 .. idx) {
	println(array[record[i]])
}

/*
실행 결과

1
2
3
4
5
*/