🖤LIS 알고리즘의 이론과 구현

1. LIS란?

LIS란 Longest Increasing Subsequence의 약자로 가장 긴 증가하는 부분 수열을 뜻한다. LIS 알고리즘 문제는 전체 수열을 주어지고, 그 안에서 가장 길고, 증가하는 부분 수열을 구해야 하는 문제들을 총칭이다. 난 부분 수열이 무엇인지부터 헷갈렸다. 따라서 먼저 수학적 배경지식을 공부하고, 마저 설명하겠다.

1-1. 부분 수열이란 무엇인가?

수열은 수가 하나의 열로 나열된 형태를 뜻한다. (행군하는 군인을 떠올려보라!) 여기서 부분수열이란 주어진 수열의 일부 항을 원래 순서대로 나열하여 얻을 수 있는 수열 을 뜻한다. 만약 전체 수열 S 가 {1,2,3,4,5,6,7,8,9,10}이라면 {1}, {2,4,6,8,10}, {2,4,6}, {8,9,10} 모두 S의 부분 수열이 된다. 특정한 조건을 만족하는 부분 수열이 전체 수열 안에서 존재할 수도 있다. 예를 들어 S에서 짝수로 이루어진 부분 수열은 {2,4,6,8,10}, {2,4,6} 등등이 해당될 것이다. 가장 긴 짝수로 이루어진 부분 수열은 {2,4,6,8,10}이 될 것이다. 7보다 큰 원소로 이루어진 부분수열은 {8,9,10}이 될 것이다.

1-2. 그렇다면 LIS 알고리즘이란?

전체 수열 S가 주어졌을 때, LIS를 구하면 된다. LIS의 길이 혹은 그 내용물을 구해야 하는 경우도 있다. 혹시 이론을 먼저 공부하지 않고, 문제를 풀어보고 싶은 사람이 있다면, 밑의 대표 문제들의 링크를 들어가서 부딪히고 오길 바란다. (티에리 앙리도 물공에 헤딩을 한다!)

2565번: 전깃줄

두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.

 

 

www.acmicpc.net

 

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

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

 

 

www.acmicpc.net

 

(가장 긴 증가하는 부분 수열 시리즈는 모두 LIS 문제이다. 실버 문제는 안 풀어서봐서 추천을 못 하겠다!)

2. 구현

2-1. DP로 구현

DP는 ‘똑똑한 완전 탐색’을 말한다. 여기서 완전 탐색 뒤에 똑똑한을 붙인 이유는 DP는 초기 주어진 값에서 어떠한 규칙성을 이용하여, 우리가 도달해야하는 값을 완전탐색보다 비교적 수월한 방법으로 찾기 때문이다. 여기서 이 규칙성을 수학 공식 형태로 표현한 것을 점화식 이라고 한다. 자 DP 설명은 나중에 더 하기로 하고, LIS에 DP를 적용해보겠다. 우리가 푸는 문제가 LIS의 길이를 구하는 문제라고 하자. (거의 모든 LIS문제의 요구사항은 LIS 길이 구하기가 기본이다! ) 먼저 주어진 수열을 배열 형태로 표현해보자. 해당 배열을 arr이라고 할 때,

index	1	2	3	4	5	6	7	8	9	10	11	12	13
value	3	4	5	6	2	3	1	7	4	3	5	6	7

이때 dp라는 배열도 만들어 보겠다. dp[i]는 arr[i]를 맨 끝 값으로 가질 때 가장 긴 증가하는 부분수열의 길이를 값으로 가진다. 표로 표현해보면 다음과 같다.

i	1	2	3	4	5	6	7	8	9	10	11	12	13
arr[i]	3	4	5	6	2	3	1	7	4	3	5	6	7
dp[i]	1	2	3	4	1	2	1	5	3	2	4	5	6

i가 4일 때를 보면 arr[4] = 6인데 해당 arr[4]를 맨 끝값으로 가지는 가장 긴 증가하는 부분수열은 {3,4,5,6}으로 dp[4] =6 이다. i = 7 일때는 arr[7] = 1 이고 arr[7]을 끝값으로 가지는 가장 긴 증가하는 부분 수열의 값은 1이다. arr[i]의 값이 같더라도, 위치에 따라 전부 다르게 생각해야한다. arr[i]는 유일 무이하다. i = 1 일때, i = 6 일때, arr[i] 값은 전부 3이지만, 위치가 다르기 때문에 만들 수 있는 증가하는 부분 수열 값이 다르다. 우리는 해당 dp의 값 중 제일 큰 값을 구하면 된다. 해당 값이 전체 수열에서 가질 수 있는 가장 긴 증가하는 부분수열의 길이이다. 여기서는 dp[13] = 6 이 LIS의 길이가 될 것이다. 그렇다면 해당 dp를 구하는 점화식은 무엇일까? 만약 dp[i]를 구한다면, 먼저 arr[0] ~ arr[i-1]에서 arr[i]보다 작은 값을 찾는다. 그 중에서 dp의 값이 제일 큰 값을 찾으면 된다. 만약 dp[x]가 해당 두 조건을 충족한다면 dp[x]는 arr[i]를 추가했을 때, 만들 수 있는 가장 긴 부분 수열이 된다. 따라서 공식은

Copy

if(i == 1) {// 배열의 맨 처음값을 조회할 경우 
dp[i] = 1}

else{
	for(int j = 1; j <=i; j++){
		if(arr[i] > arr[j]){
			 dp[i] = Math.max(dp[i], dp[j]+1);
		}
	}
}

가 된다. (사실 점화식은 아예 수학공식으로 표현해야하는데, 해당 LIS의 경우 점화식을 찾기가 어려웠고, 구상하기도 만만치 않았다. 찾으면 연락 바란다.)

DP를 이용한 LIS 풀이는 하나의 dp[i] 를 구할 때마다 arr 배열을 i보다 작은 인덱스 범위까지 싹 다 돌아야 한다. 그래서 최악의 시간 복잡도는 O(N^2)가 나온다.

2-2. 이분 탐색으로 구현

이분탐색 구현은 우리가 조작하는 배열에 다른 의미를 담는다. 자 주어진 전체 수열은 똑같다고 하겠다.

index	1	2	3	4	5	6	7	8	9	10	11	12	13
value	3	4	5	6	2	3	1	7	4	3	5	6	7

이때 이분탐색을 위해 다음과 같은 배열D를 하나 더 만든다.

i	1	2	3	4	5	6
D[i]	1	3	4	5	6	7

D의 뜻은 다음과 같다. i들은 해당 전체 수열에서 구할 수 있는 증가하는 부분 수열의 길이이다. D[i]는 해당 부분 수열의 맨 끝 값이 될 수 있는 수 중 최소값이다. 최소값이기 때문에 전체수열 S를 순회할 수록 갱신된다. 맨 처음에 D[1]은 다음과 같았을 것이다.

i	1	2	3	4	5	6
D[i]	3	(아직 만들어지지 않음)	(아직 만들어지지 않음)	(아직 만들어지지 않음)	(아직 만들어지지 않음)	(아직 만들어지지 않음)

그리고 i = 4까지 가면

i	1	2	3	4	5	6
D[i]	3	4	5	6	(아직 만들어지지 않음)	(아직 만들어지지 않음)

이 될 것이고, i = 5 일때,

i	1	2	3	4	5	6
D[i]	2	4	5	6	(아직 만들어지지 않음)	(아직 만들어지지 않음)

D[1]이 갱신된다. 왜냐하면 arr[5] = 2 이고 해당 값을 끝 값으로 가지는 가장 긴 증가하는 부분 수열의 길이는 1이기 때문이다. 또한 원래의 D[1] 값보다 작으므로 갱신된다. 이런식으로 값이 쭉 갱신되고, arr의 마지막 값까지 순회하면 배열 D가 완성된다. 이때 배열 D의 마지막 인덱스의 값 즉 배열 D의 길이가 LIS의 길이가 된다. D[i]를 최소값으로 갱신하는 이유는 나중에 해당 수를 참고하여 더 긴 증가하는 부분 수열이 나올 수 있기 때문이다. 갱신에는 이분탐색이 쓰인다. 현재 9번째를 조회하고 arr[9] = 4 이다. 현재 배열 D는 아래와 같다.

i	1	2	3	4	5	6
D[i]	3	4	5	6	7	(아직 만들어지지 않음)

그러면 arr[9] = 4는 해당 D 값들 사이에서 이분탐색이 진행된다. 4는 D[2]와 D[3] 사이의 값이므로 해당 위치까지 갈 것이다. 하지만 D[2]보다 arr[9]가 작지 않으므로 갱신은 이루어지지 않는다. 이제 다음 값을 확인하며 배열 전체를 순회한다. 이분탐색의 경우에는 DP 풀이처럼 배열의 값 하나하나 찾기 위해 그전까지의 모든 arr값을 순회하는 시간 낭비를 하지 않는다. 해당 순회는 이분탐색이 해결해주기 때문이다. 따라서 최악의 시간 복잡도는 조금 더 개선되어서 O(N * logN) 이다.