[알고리즘 이론] LIS(Longest Increasing Subsequence) 최장 증가 부분 수열

이론

1. LIS이란?

 LIS 개념을 이해하기 전에 기본적으로 DP(동적 계획법)또는 이분탐색을 알아야 된다. DP 에 관련 내용은 아래 사이트에 참조하면된다.

https://jih3508.tistory.com/89

[알고리즘 이론] 동적계획법(Dynamic Programming, DP)

  LIS, 최장 증가 부분 수열은 나열된 배열이나 리스트에서 원소를 몇개 제외하고 오름차순또는 내림차순으로 가징 긴 수열을 말한다 예를 들어 {1, 5, 3, 6, 7, 9, 4, 2, 10}  배열이 있다고 가정 하자 몇 개의 원소를 제외 하고 오름 차순으로 나올 배열은

• {1, 3, 6, 7, 9, 10} (5, 4 ,2  제외)
• {1, 5, 6, 7, 9, 10} (3, 4, 2 제외)
• {1, 3, 4, 5, 10}(5, 6, 7, 9 제외)
• {1, 4, 10}(5, 3, 6, 7, 9, 2 제외)
• {1, 2, 10}(5, 3, 6, 7, 9, 4 제외)

등 여러 가지가 나타 낼수 있는데. 이중 가장 긴 수열은 {1, 3, 6, 7, 10, 11}, {1, 5, 6, 7, 10, 11} 이다.

 방법은 2가지 있는데 일단 먼저 DP로 구하는 방법을 설명하고 나중에 이분탐색으로 하는 방법을 설명 하겠다.

2. DP로 구하는 방법

index	0	1	2	3	4	5	6	7	8
array	1	5	3	6	7	9	4	2	10

 위의 예시를 표로 표현 한것이다.   DP로 LIS 오름차순으로 구하는 방법을 설명 하겠다. DP는 간단하게 정의 한다면 최적의 방법으로 중복 연산하는 부분 피해서 다른값을 가져와서 처리하는 방법이고 점화식으로 통해서 구현하는 알고리즘이다. 일단  0번째 인덱스부터 값이 어떻게 되어가는지 확인을 해보자.

0번째 인덱스

일단 보면 index 각 인덱스의 값, 연속된 배열 그리고 뒤에 원소를 삭제시 가장 길게 나오는 길이가 나와있다. 0번째 인덱스를 보면 뒤에 아무것도 없어서 맨앞에 숫자만 추가하면된다.

index	0	1	2	3	4	5	6	7	8
array	1	5	3	6	7	9	4	2	10
sequence	1
length	1

 

1번째 인덱스

1번째 값은 5이다. 뒤에 숫자가 1이기 때문에 그냥 5를 추가하면된다.

index	0	1	2	3	4	5	6	7	8
array	1	5	3	6	7	9	4	2	10
sequence	1	5
length	1	2

 

2번째 인덱스

2번째 인덱스 값은 3이다. 하지만 5보다 크다. 그래서 5를 지운다.

index	0	1	2	3	4	5	6	7	8
array	1	5	3	6	7	9	4	2	10
sequence	1	3
length	1	2

3번째 인덱스

3번째 인덱스를 보면 6이다. Dp 배열에 마지막으로 저장한 값이 3이기 때문에 3보다 커서 6을 추가한다.

index	0	1	2	3	4	5	6	7	8
array	1	5	3	6	7	9	4	2	10
sequence	1	3	6
length	1	2	2	3

4, 5번째 인덱스

4,5 번째 인덱스도 7, 9 순서대로 오름차순이고 dp 배열의 마지막 숫자 6보다 커서 추가하면된다.

index	0	1	2	3	4	5	6	7	8
array	1	5	3	6	7	9	4	2	10
sequence	1	3	6	7	9
length	1	2	2	3	4	5

 

6, 7번째 인덱스

 6번째 인덱스 부터는 중요하게 봐야 한다. 이전 배열중 4보다 작은값은 가장 큰 값은 3이다. 하지만 3일때 길이는 2이고 DP의 마지막 배열의 값은 9이다. 9일때 길이는 5가 나왔다. 길이를 비교하면 5번째 인덱스보다 값이 작을 뿐만 아니라 길이도 작아서 추가가 안된다.7번째 인덱스도 마찮가지이다. 7인덱스 이전 값중 2보다 작은값에서 가장 큰 값은 1이다. 1의 길이 는 1이다. 5번째 인덱스보다 값하고 길이도 작아서 추가가 안되다.

index	0	1	2	3	4	5	6	7	8
array	1	5	3	6	7	9	4	2	10
sequence	1	3	6	7	9
length	1	2	2	3	4	5	3	2

8번째 인덱스

8번째 인덱스는  DP 배열의 9보다 크기때문에 추가만 하면된다.

index	0	1	2	3	4	5	6	7	8
array	1	5	3	6	7	9	4	2	10
sequence	1	3	6	7	9	10
length	1	2	2	3	4	5	3	2	6

 

 

 예시로 첫번째 부터 마지막까지 탐색해서 돌아가는 방식을 설명했다. 이제 남은것은 점화식이다. 6번째 인덱스 기준으로 보면 6번째 이전 인덱스 보다 값중 가장 큰 값은 2번째 인덱스 이고  2번째 인덱스에서 길이를 +1만 추가하면된다. 그래서 코드로 설명 한다면 자기 자신보다 이전 인덱스를 탐색한것중 현재 인덱스보다 작은 값중 길이가 가장 긴것을 가져오면되고 각 인덱스의 길이를 다 구했으면 그중 가장 큰 값을 가져오면 된다.

DP로 구현했을때 시간복잡도는 O(n^2)으로 보면된다.

Code

python

array = [1, 5, 3, 6, 7, 9, 4, 2, 10]
dp= [1] * len(array) # 각 인덱스 값에서 가장 길게 표현 할수있는 길이


for i in range(len(array)):
    for j in range(i):
        if array[i] > array[j]:
            dp[i] = max(dp[j] + 1, dp[i]) # 현재 탐색중 길이와 이전 탐색 길이중 긴것만 추가한다.
    
print(max(dp))

Java

import java.util.Arrays;

public class Main {

	public static void main(String[] args) {
		int[] array = {1, 5, 3, 6, 7, 9, 4, 2, 10};
		int[] dp = new int[array.length];
		Arrays.setAll(dp, i -> 1); // 최소 나올수는 있는 길이가 1이기 때문에 1로 설정한다.
		for(int i = 0; i < array.length; i++) {
			for(int j = 0; j < i; j++) {
				if(array[i] > array[j]) {
					dp[i] = Math.max(dp[j] + 1, dp[i]);
				}
			}
		}
		
		System.out.println(Arrays.stream(dp).max().getAsInt());
						
	}
			
}

내림차순으로 구할때는 크기 비교를 반대로 하면 된다.

3. 이분탐색

 이번에는 이분탐색으로 하는 과정을 보겠다. DP방식보다 구현 난이도와 이해도가 좀 높지만 처리 속도면에서는 빠르다고 볼 수가 있다. 

index	0	1	2	3	4	5	6	7	8
array	1	5	3	6	7	9	4	2	10

 다시 위에 데이터로 예제로 하겠다. 이분 탐색이라는 개념을 알아야 하는데 간단하게 설명 한다면 범위에서 중간값을 가르켜서 원하는 값이 날올때 까지 범위를 좁히고 그 범위의 중간값으로 찾는 방식이라고 설명 할수 있다. DP 탐색은 O(N)이였는데 이분 탐색은 O(logN)라는 놀라운 처리 속도를 가지고있다. 이분 탐색을 자세히 알고 싶으면 밑에 사이트를 참조해라,

https://namu.wiki/w/%EC%9D%B4%EC%A7%84%20%ED%83%90%EC%83%89

이진 탐색 - 나무위키

 이제 중요한 부분은 이분 탐색은 어디서 처리하는 것인데 인덱스 전체 탐색까지는 같지만 DP는 이전 인덱스보다 몇개 큰지만 세워 왔지만 이분 탐색은 따로 수열 배열을 만들어서 배열 안에서 몇번째로 큰지 알아 내는 것이다. 그리고 이분 탐색은 전제 조건은 정렬된 데이터인데 LIS는 증가는 수열이라서 오름차순 또는 내림차순으로 데이터를 저장하기 때문에 이분 탐색할수 있는 조건이 맞다.  여기 까지는 접근 방법이고 알고리즘 적용하는 방법을 설명하겠다.

1.  내림차순 또는 오름차순으로 정렬할 수열(LIS), 배열 또는 리스트를 만든다.
2. 현재 인덱스와  LIS 배열에서 맨 뒤에 값이랑 비교한다.
3. 현재 인덱스가 LIS 배열에서 맨 뒤에 값보다 크면 LIS 배열 뒤에 값을 추가한다. 작으면 이분 탐색해서 현재 인덱스 값에서 작거나 같은 값의 위치를 찾는다.(Lower Bound Search)
4. 이분 탐색으로 찾은 위치를 현재 값으로 넣는다. → 자신보다 얼마나 큰지알기 위해서와 다음 인덱스가 참조하 수 있기 때문에 치환 한다.

간단하게 어떤식으로 돌아가는지 설명 했다. 하지만 이해하기 힘든 분이 있어서.. 직접 돌아 가는 방식을 설명 하겠다.

0, 1번 째 인덱스

 밑에 표보면  count 대신 location으로 변경 되었다. location은 저장할 index 위치라고 보면된다.

 LIS 배열에서 증가하는 부분에서 값이 없기 때문에 LIS 배열 값을 추가만하면된다. 1번째 인덱스도 보면 1보다 크기 때문에 LIS 배열에 추가만 하면된다.

index	0	1	2	3	4	5	6	7	8
array	1	5	3	6	7	9	4	2	10
sequence	1	5
location	0	1

2번째 인덱스 

 여기부분은 집중해서 보면된다. 2번째 인덱스 값은 3이다. 그리고 LIS배열 맨 뒤의 값은 5이다. 3은 5보다 크기 때문에

3보다 작거나 큰 값중 가장 큰 값을 찾으면 된다. 그럼 0번째 인덱스이다. 0번째 인덱스 값을 3으로 바꾸면 된다.

index	0	1	2	3	4	5	6	7	8
array	1	5	3	6	7	9	4	2	10
sequence	3	5
location	0	1	0

3, 4, 5번 째 인덱스

 3 ,4 ,5번 째 인덱스값은 LIS 배열 5보다 크고 차례대로 크기가 커져서 LIS 배열뒤에 추가만 해주면 된다.

index	0	1	2	3	4	5	6	7	8
array	1	5	3	6	7	9	4	2	10
sequence	3	5	6	7	9
location	0	1	0	2	3	4

6번 째 인덱스

 6번째 인덱스의 값은 4이다. LIS 배열 맨 마지막 값은 9라서 이분 탐색으로 4보다 작거나 같은 값을 찾으면 된다. 그러면 0번째 인덱스라는 것을 알수 있다.

index	0	1	2	3	4	5	6	7	8
array	1	5	3	6	7	9	4	2	10
sequence	4	5	6	7	9
location	0	1	0	2	3	4	0

7번 째 인덱스

 7번 째 인덱스를 보면 LIS 값보다 큰 값이 없다. 아무것도 없을 때는 location 0에 저장 하고 넘어가면된다. 이유는 2도 맨 앞에 증가하는 수열로 올 수 있기 때문이다.

index	0	1	2	3	4	5	6	7	8
array	1	5	3	6	7	9	4	2	10
sequence	4	5	6	7	9
location	0	1	0	2	3	4	0	0

8번 째 인덱스

 마지막 인덱스는 LIS 배열 맨 뒤에 값보다 크기 때문에 LIS 값을 추가만 하면 된다.

index	0	1	2	3	4	5	6	7	8
array	1	5	3	6	7	9	4	2	10
sequence	4	5	6	7	9	10
location	0	1	0	2	3	4	0	0	5

Code

Python

array = [1, 5, 3, 6, 7, 9, 4, 2, 10]
sequense = [array[0]]

for num in array[1:]:
    if sequense[-1] < num:
        sequense.append(num)
    else:
        start = 0
        end = len(sequense) - 1
        while start <= end:
            mid = (start + end) // 2
            if sequense[mid] >= num:
                end = mid - 1
            else: start = mid + 1
        sequense[start] = num

 위에 정석대로 푸는 방법이 있지만 Python 라이브러리중 bisect이라는 모듈이 있다. bisect_left 함수 사용하면 lower Bound Search가 되니 알아 두도록 하자..

import bisect
array = [1, 5, 3, 6, 7, 9, 4, 2, 10]

#처음에 맨 뒤에 값이랑 비교하기위해서 수열 부분에 첫번째 인덱스 값이 옴
sequense = [array[0]]
for num in array[1:]:
    if sequense[-1] < num:
        sequense.append(num)
    else:
        sequense[bisect.bisect_left(sequense, num)] = num

Java

 자바는 파이썬처럼 list가 아닌 배열로 처리해야 한다. 그래서 sequese 배열 사이즈 알기위해서 size라는 변수를 추가로 선언했다.

public class Main {
	

	public static void main(String[] args)  {
		
		int[] array = {1, 5, 3, 6, 7, 9, 4, 2, 10};
		int[] sequense = new int[array.length];
		
		// 처음에 맨 뒤에 값이랑 비교하기위해서 수열 부분에 첫번째 인덱스 값이 옴
		sequense[0] = array[0];
		int start, end, mid;
		int size = 0; // sequense의 현재 배열 사이즈
		for(int i = 1; i < N; i++) {
			if (sequense[size] < array[i]) {
				size++;
				sequense[size] = array[i];
			}else {
				start = 0;
				end = size;
				while(start <= end) {
					mid = (start + end) / 2;
					if (sequense[mid] >= array[i]) {
						end = mid - 1;
					}else {
						start = mid + 1;
					}
				}				
				sequense[start] = array[i];
			}
		}
	}
		
}

 

LIS 관련 추천 문제

가장 긴 증가하는 부분 수열

난이도: Silver2

사이트: https://www.acmicpc.net/problem/11053

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

코드:
가장 기본적인 문제이다.

[BAEKJOON]11722 가장 긴 감소하는 부분 수열

 

가장 긴 감소하는 부분 수열

난이도: Silver2

사이트: https://www.acmicpc.net/problem/11722

코드:   https://jih3508.tistory.com/249

[BAEKJOON]11722 가장 긴 감소하는 부분 수열

 

위에 문제에서 반대인 경우 문제이다. 비교하는 코드만 다르게 하면된다.

 

전깃줄

난이도: Gold5

사이트: https://www.acmicpc.net/problem/2565

2565번: 전깃줄

코드: https://jih3508.tistory.com/47

[BAEKJOON] 2565 전깃줄

 

처음에 보면 dp와 LIS랑 연관성을 짓기가 힘들것이다. 하지만 이런 문제를 풀어보면 문제 보는 시야가 늘어 날것이다.

가장 긴 바이토닉 부분 수열

난이도: Gold4

사이트: https://www.acmicpc.net/problem/11054

11054번: 가장 긴 바이토닉 부분 수열

코드: https://jih3508.tistory.com/48 

[BAEKJOON] 11054 가장 긴 바이토닉 부분 수열

 

코딩테스트에서 나올만한 문제이니 꼭 풀어 보길 바란다.

가장 긴 증가하는 부분 수열 2 

 난이도 : Gold2

사이트: https://www.acmicpc.net/problem/12015

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

코드:  https://jih3508.tistory.com/79

[BAEKJOON] 12015 가장 긴 증가하는 부분 수열 2

이 문제는 DP로 안풀려서 이분탐색 방식으로 풀어야 될것이다.