[알고리즘] 가장 긴 증가하는 부분 수열 LIS - DP & 이진탐색 (Java)

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

LIS(Longest Increasing Subsequence)는 불연속 상관없이 가장 긴 증가하는 부분 수열을 구하는 알고리즘이다.

• 예시로, 수열 A = {10, 20, 10, 30, 20, 50}이 있다고 하면 해당 수열의 LIS는 {10, 20, 30, 50} 이다.

 

풀이 방법으로는 DP를 활용한 LIS, 이진탐색을 활용한 LIS 두 가지가 있다.

• DP는 단순하지만 시간복잡도가 O(n^2)을 가진다.
• 이진탐색을 활용하면 시간복잡도를 O(nlogn)을 가진다.

 

1. DP로 풀이하는 방법

dp는 1차원 배열로 dp[i]에는 0~i 증가하는 부분 수열의 크기를 나타낸다.

• dp[i] = 0~i의 증가하는 부분 수열 크기

 

수열 A = {10, 20, 10, 30, 20, 50} 

 

10	20	10	30	20	50
1	2	1	3	2	4

 

설계

1. 이중 포문을 설계하여 각 수를 직접 비교해가면서 증가하는 부분 수열의 크기를 카운트해준다.
   1. i : 1 ~ n-1
   2. j : 0 ~ i-1
2. 가장 긴 증가하는 부분 수열 LIS는 dp[i] 중 최댓값을 선택해 출력해주면 된다.

 

시뮬레이션

간단하게 A = {10, 20, 10, 30}인 배열을 시뮬레이션 돌려보자.

 

1) i = 3, j =0 일때, 30 > 10 이므로 dp[3] = Math.max(dp[3],dp[0]+1) =2

10	20	10	30
1	2	1	2

 

2) i = 3, j =1 일때, 30 > 20 이므로 dp[3] = Math.max(dp[3],dp[1] +1) = 3

10	20	10	30
1	2	1	3

 

3) i = 3, j =2 일때, 30 > 10 이므로 dp[3] = Math.max(dp[3],dp[2] +1) = 3 

• 이번에는 기존의 값이 더 크므로 그대로 값을 유지한다.

10	20	10	30
1	2	1	3

 

풀이코드

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

// #11053 dp LIS 가장 긴 증가하는 부분 수열 
import java.io.*;
import java.util.StringTokenizer;

public class LIS {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		
		StringTokenizer st= new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int[] dp = new int[n];
		
		dp[0] = 1;
		for(int i=1; i<n; i++) {
			dp[i] = 1;
			for(int j=0; j<i; j++) {
				if(arr[i] > arr[j]) {
					dp[i] = Math.max(dp[i], dp[j]+1);
				}
			}
			
		}
		int max =-1;
		for(int i=0; i<n; i++) {
			max = Math.max(max, dp[i]);
		}
		System.out.println(max);
	}
}

 

2. 이진탐색으로 풀이하는 방법

수열의 크기(100만)가 크게 주어질 경우 DP를 통한 풀이는 O(n^2)으로 시간초과가 발생한다. 효율성을 올리기 위해 이진탐색을 통한 최적하 작업을 이뤄 시간복잡도를 O(nlogn)으로 줄여준다.

 

이진탐색은 정렬된 배열에서 특정한 값을 찾아내는 알고리즘인데 어떻게 오름차순으로 정렬되지도 않은 수열의 LIS를 찾을 수 있을까? 

 

구상 (기준이 되는 데이터 정하기)

정수 수열이라는 것만 알고 그 크기 등은 모르는 상태인 수열 arr을 입력받았다. 이제 이 수열을 하나씩 건너가며 LIS를 만들어나간다고 하자.

 

1) 4번의 탐색을 통해 [5, 6, 1, 2]의 원소를 알아냈다.

☛ 현재 까지의 LIS [5,6], [1,2]로 2이다.

 

2) 다음 탐색을 통해 7을 찾아냈다. [5, 6, 7, 1, 2]

☛ 현재 까지의 LIS [5,6,7]로 3이다.

 

계속해서 연산을 진행한다고 할 때 현재까지 구한 LIS 정보는 의미가 있는지 없는지 두 가지 경우로 나눠볼 수 있다.

• 의미없다. 
  • 원 수열이 [5,6,7,1,2,3,4]이게 되면 [1,2]가 최종적인 LIS가 될 수 있다. 이때 중간 LIS 수열 [5,6,7]의 정보는 무의미해진다.
• 의미있다.
  • 원 수열이 [5,6,7,1,2]에서 끝나버린다면 현재까지의 LIS인 [5,6,7]의 크기 3이 곧 답이 된다.

이렇게 미지의 확률로 의미의 여부가 갈리게 된다. 그렇기 때문에 중간에 생기는 LIS가 무의미할 수도 의미있을 수도 있는 상황이기에 애매하다.

 

그렇기 때문에 매 탐색을 통해 얻어내는 LIS의 데이터에 의존하기에는 불확실한 미래가 펼쳐진다. 그럼 의미있는 상황 데이터들만 최적화되게 가져올 수 있는 방법은 없을까?

 

매 탐색마다 길이가 len인 LIS들의 마지막 값중 최솟값

여기까지의 불완전한 수열([5,6,7,1,2])까지만 봤을 때도 확실한 것들이 있다.

• 길이가 1인 증가 부분수열들의([5],[6],...[2]) 마지막 값(5,6,7,1,2) 중 최소의 값은 1이고,
• 길이가 2인 증가 부분수열들의([5,6],[1,2]) 마지막 값(6,2) 중 최소의 값은 2이다.
• 길이가 3인 증가 부분수열의([5,6,7]) 마지막 값(7) 중 최소의 값은 7이다.

→ 매번 탐색을 해나갈 때 마다 증가 부분수열의 길이가 같다면 이때 마지막 값의 크기가 작은 것의 정보를 유지하면서 탐색을 이어나가야 된다.

 

왜 마지막 값의 크기가 작은 것의 정보를 유지해야하지?

• 가령 배열의 첫 네 원소가 [5,6,1,2]일 때 길이가 2인 증가 부분수열은 [5,6]과 [1,2]이 있다.
• 그 다음 수가 무엇이 될지는 모르겠지만 작은 정보를 유지할 때는 LIS를 문제없이 구할 수 있다. 가령 원 수열의 바로 뒤의 수이자 마지막 수가 3일 때나 11111일 때 모두 [1,2]는 LIS를 만들어낼 수 있다.
• ([1,2,3],[1,2,11111]) 하지만 [5,6]은 3일 때 LIS를 이어가지 못한다.([5,6,3])
• 즉, 같은 크기의 증가수열에서 마지막 값 중 최솟값만 기억하면 문제를 풀어낼 최적화된 단서를 찾을 수 있다.

 

따라서 memo 1차원 배열은 길이가 len인 증가 부분수열들의 마지막 값 중 최솟값을 저장해준다.

• memo[len] = 0~i의 arr의 원소배열 중 LIS의 길이가 len인 부분수열들의 마지막 값 중 최솟값
  • memo[0] = 길이가 1인 LIS 부분 수열 중 최솟값
  • memo[1] = 길이가 2인 LIS 부분 수열 중 마지막 값 중 최솟값
  • 이런식으로 증가 폭을 최대한 줄여 memo를 오름차순인 LIS배열로 값을 할당시키는 것이다.
    • memo배열은 오름차순으로 정렬된 배열이므로 이진탐색이 가능해진다.

 

설계

1. 새로운 숫자 num이 현재 memo[len]의 값보다 크다면 새로운 LIS가 갱신된다. if(num > lastNum) 
   1. memo[++len] = num 
2. 새로운 숫자 num이 수열의 최솟값과 최댓값의 사이에 있는 값이라면 이진탐색을 통해 기존 값을 바꿔준다.
   1. num = 3이면 이는 1,2,7보다는 뒤에 등장하는 수이고 또 1,2보다 크기보다는 크고 7보다는 작은 값이다.
   2. 이진탐색을 통해 memo[i-1] < num <= memo[i]인 곳을 찾아 memo[i] = num을 갱신해준다.
3. 모든 탐색이 끝난 후 len이 해당 배열의 LIS 길이가 된다.

 

시뮬레이션

arr={5, 6, 7, 1, 2, 3, 4}

i : 0 ~ 3

i : 4 ~ 6

 

위와 같은 풀이로 memo[] 1차원 배열에 조건에 맞춰 수를 탐색한다면 최종적으로 이 memo 배열은 오름차순으로 정렬된 상태로 유지되므로 이진탐색을 통한 탐색이 가능해지는 것이다.

 

그렇다면 O(N)의 순차탐색이 아닌 O(logN)의 이진 탐색을 써서 진행하는 것이 시간복잡도를 크게 줄일 수 있어 효율적으로 풀 수 있다.

 

DP를 통한 구현법은 2중 포문으로 시간복잡도가 O(N^2)이었는데 이와 같은 이진탐색을 통한 최적화된 구현법은 원배열을 순회 O(N), 각 순회에서 이진 탐색 O(logN)으로 최종적으로 시간복잡도가 O(NlogN)로 DP보다 더 효율성이 있는 알고리즘 설계가 가능해진다.

 

풀이코드

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

import java.io.*;
import java.util.StringTokenizer;

public class Main {
	
	static int[] memo;
	static int INF = Integer.MIN_VALUE;

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n];
		
		StringTokenizer st= new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		memo = new int[n+1];
		int len=0;
		int idx=0;
		for(int i=0; i<n; i++) {
			if(arr[i] > memo[len]) {
				len +=1;
				memo[len] = arr[i];
			}else {
				idx = binarySearch(0,len, arr[i]);
				memo[idx] = arr[i];
			}
		}
		System.out.println(len);
	}
	
	static int binarySearch(int left, int right, int key) {
		int mid =0;
		while(left<right) {
			mid = (left+right)/2;
			if(memo[mid] < key) {
				left = mid+1;
			}else {
				right = mid;
			}
		}
		return right;
	}
}