[LIS] 최장 증가 부분 수열(Longest Increasing Subsequence)

알고리즘 문제를 풀다보면 부분수열, 부분증가 수열등 여러 수열문제를 접할 수 있다. 그중

임의의 수열중 가장 긴 증가수열을 만들 수 있는 방법인 최장증가 부분 수열, LIS 알고리즘에 대해 기록한다.

 

1. 그림 예시로 보는 LIS 이해하기

다음과 같은 수열이 있다고 했을 때 우리는 다양한 방법으로 부분 증가 수열을 구할 수 있다.

임의의 수열

ex) 인덱스 0부터 시작하는 부분 증가 수열

index 0 부터 증가수열

ex) 인덱스 1부터 시작하는 부분 증가 수열

index 1 부터 증가수열

ex) 인덱스 2부터 시작하는 부분 증가 수열

index 2 부터 증가수열

ex) 인덱스 3부터 시작하는 부분 증가 수열

index 3 부터 증가수열

 

위처럼 여러 부분 증가 수열중 가장 긴 부분 증가 수열은 인덱스 0부터 시작하는 수열(length : 5)이 된다.

---

2. LIS 알고리즘 O(N²)

 

그렇다면 해당 알고리즘을 어떻게 코드로 구현할 수 있을까? 여기서는 그림과 JAVA 코드를 토대로 해당 알고리즘을 설명할 것이다.

먼저, 다음과 같이 크기가 7인 리스트가 있다.

Index는 헤딩 리스트의 인덱스 값을 나타내며, List에는 각 수열의 값을 보여준다. 마지막으로, DP에는 현재 인덱스 까지의 까지의 수열중 만들어질 수 있는 가장 긴 수열의 길이를 담아준다.

 

1) DP 인덱스 0일때

인덱스가 0일때 DP[0] = 자기 자신의 길이 즉 1이 되게 된다. 

 

2) DP 인덱스가 1일때

인덱스가 1일때는 두가지의 선택지가 있다.

(1) 인덱스 1전까지의 값들 중 List[1]보다 작은 값이 있는 경우 : 이전 값의 수열길이에 1을 더한다(DP[1] = DP[0] + 1)

(2) 인덱스 1의 값이 가장 작은 경우 : DP[1] = 1;

 

3) DP 인덱스가 2일때

for(int index = 0; index < DP[2].Index; index++){
	if(List[index] < List[DP[2].Index]){
    	DP[2] = Math.max(DP[2], DP[index] + 1);
    }
}

 

0부터 인덱스 2 전까지의 인덱스중 해당 수가 현재 인덱스(2)의 수보다 작을 경우 DP[2] = DP[index] + 1이다.

[0] : DP[2] = DP[0] + 1;

[1] : DP[2] = Math.max(DP[2], DP[1] + 1);

 

4) DP 인덱스가 3일때

for(int index = 0; index < DP[3].Index; index++){
	if(List[index] < List[DP[3].Index]){
    	DP[3] = Math.max(DP[3], DP[index] + 1);
    }
}

 

0부터 인덱스 3 전까지의 인덱스중 해당 수가 현재 인덱스(3)의 수보다 작을 경우 DP[3] = DP[index] + 1이다.

[0] : DP[3] = DP[0] + 1;

[1] : 수가 증가하지 않는다.

[2] : 수가 증가하지 않는다.

 

5) DP 인덱스가 4일때

for(int index = 0; index < DP[4].Index; index++){
	if(List[index] < List[DP[4].Index]){
    	DP[4] = Math.max(DP[4], DP[index] + 1);
    }
}

 

0부터 인덱스 4 전까지의 인덱스중 해당 수가 현재 인덱스(4)의 수보다 작을 경우 DP[4] = DP[index] + 1이다.

[0] : DP[4] = DP[0] + 1;

[1] : Math.max(DP[4], DP[1] + 1);

[2] : Math.max(DP[4], DP[2] + 1);

[3] : Math.max(DP[4], DP[3] + 1);

 

6) DP 인덱스가 5일때

for(int index = 0; index < DP[5].Index; index++){
	if(List[index] < List[DP[5].Index]){
    	DP[5] = Math.max(DP[5], DP[index] + 1);
    }
}

 

0부터 인덱스 5 전까지의 인덱스중 해당 수가 현재 인덱스(5)의 수보다 작을 경우 DP[5] = DP[index] + 1이다.

[0] : DP[5] = DP[0] + 1;

[1] : 수가 증가하지 않는다.

[2] : 수가 증가하지 않는다.

[3] : 수가 증가하지 않는다.

[4] : 수가 증가하지 않는다.

 

7) DP 인덱스가 6일때

for(int index = 0; index < DP[6].Index; index++){
	if(List[index] < List[DP[6].Index]){
    	DP[6] = Math.max(DP[6], DP[index] + 1);
    }
}

 

0부터 인덱스 6 전까지의 인덱스중 해당 수가 현재 인덱스(6)의 수보다 작을 경우 DP[6] = DP[index] + 1이다.

[0] : DP[6] = DP[0] + 1;

[1] : Math.max(DP[6], DP[1] + 1);

[2] : Math.max(DP[6], DP[2] + 1);

[3] : Math.max(DP[6], DP[3] + 1);

[4] : Math.max(DP[6], DP[4] + 1);

[5] : Math.max(DP[6], DP[5] + 1);

---

3. 최장 증가 수열과 그 길이를 구하는 방법

 

1) 최장 증가 수열의 길이

먼저 최장 증가 수열의 길이는 위의 방식대로 구해진 DP리스트에서 가장 큰 값이 최장증가 수열의 길이가 된다. 즉, 위 수열에서 만들어질 수 있는 부분 수열중 가장 길이가 긴 수열의 길이는 5이다.

 

2) 최장 증가 수열 리스트

보통 최장 증가 수열을 만들때 위와 같이 잘 해놓고 앞에서 부터 수열을 만드는 실수를 하곤 한다. 하지만 그 방법으로는 현재 들어간 수가 최장 증가 부분 수열의 값에 속하는지 아닌지 확인할 길이 없기 떄문에 항상 뒤에서 부터 앞으로 확인해야한다.

 

Result : {10, 20, 30, 50, 60}