[BOJ] 백준 12015번 가장 긴 증가하는 부분 수열2 LIS - 이진탐색 (Java)

#12015 가장 긴 증가하는 부분 수열 2 (LIS)

난이도 : 골드 2

유형 : DP

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

▸ 문제

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

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

▸ 입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

▸ 출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

문제 풀이 

LIS DP를 통한 구현법으로 풀이를 하면 시간초과가 발생한다. 

왜냐하면 이번 문제에서는 수열 A의 크기가 (1 ≤ N ≤ 1,000,000)이기 때문에 이중 포문으로 DP로 풀이를 하면

1,000,000 x 1,000,000 -> 1조번의 연산이 이루어지기 때문이다.

 

이진 탐색을 통한 최적화

그래서 필요한 방법이 바로 이진탐색이다. 이 방식은 동적 계획법(DP) 알고리즘과는 완전 다르게 접근해야 한다.

 

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

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

 

어떤 수열의 원소를 4개를 먼저 살피니 [5,6,1,2]였다고 하자.

 

1) 그래서 현재까지의 LIS :  [5,6], [1,2] -> 2

뒤에 더 많은 숫자가 있지만 일단은 지금의 정보가 최선이다.

 

다음엔 어떤 수열의 첫 5개의 숫자가 다음과 같다고 하자 [5,6,7,1,2]

2) 현재까지의 LIS :  [5,6,7] -> 3

 

계속해서 연산을 해나간다고 할 때 현재까지의 LIS 정보가 의미있을까?

 

상황에 따라 다른데 크게 두 가지 경우로 나눌 수 있다.

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

쉽게 말하자면 모든 탐색이 끝난 시점에 나온 최종 LIS 수열에 [5,6,7]이 포함되는 경우와 아닌 경우로 나뉘는데 뒤에 미지의 확률을 어떻게 알고 이 값을 저장하냐 이말이다.

 

현재까지 주어진 수 이상의 미지의 수열은 아직 모르는 상태 그냥 확률은 반반이라는 소리이다.

 

그렇기 때문에 중간에 생기는 LIS가 무의미할 수도, 의미있을 수도 있는 상황이기에 애매하다. 의미 있는 상황만 최적화되게 가져올 수 있는 방법은 없을까?

 

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

• 길이가 1인 증가 부분수열들의([5],[6],...[2]) 마지막 값 중 최소의 값은 1이고,
• 길이가 2인 증가 부분수열들의([5,6],[1,2]) 마지막 값 중 최소의 값은 2이다.
• 길이가 3인 증가 부분수열의([5,6,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[i] = 길이가 i인 증가수열들 중에서 최소의 마지막 값

 

원 배열을 [5,6,7,1,2]까지 진행했을 때 memo배열은 다음과 같을 것이다.

• memo=[1,2,7,inf,inf]
• 여기서 memo[i] != inf인 i의 최댓값이 LIS의 길이가 된다. 그래서 현재까지의 LIS는 3이다. i=3, [5,6,7]

 

이러한 방식으로 조건을 적절하게 써서 연산하면 다음과 같다. 

설계

다음에 올 숫자를 num이라고 하자. 지금까지 찾은 LIS의 길이를 len, memo[len]의 값을  lastNum이라고하자.

1. 다음에 올 숫자(num)가 현재 마지막 값 중 최솟값(lastNum)보다 크다면? 새로운 LIS가 갱신된다.
   1. if(num > lastNum), memo[len+1] = num
      1. ex) num =10,  10 > 7 이기 때문에 LIS 갱신 ->  C=[1,2,7,10,inf]
2. 다음에 올 숫자(num)가 수열의 최솟값과 최댓값 사이의 값이라면?
   1. num = 3이면, 이는 1,2,7보다는 뒤에 등장하는 수이고 또 1,2보다 크기보다는 크고 7보다는 작은 값이다.
   2. 우리는 지금 가장 긴 증가하는 부분 수열을 찾고있지 않은가?
      1. 탐색이 다 끝나지 않은 지금 시점에서 [1,2,7]을 갖고있는 것보다는  [1,2,3]을 갖고 있는 것이 뒤에 남은 탐색에 있어 더 유리할 것이다.
      2. 만약 3 다음에 5가 온다면? [1,2,3,5]로 값 갱신이 가능할 것이다. 하지만 7이었다면 그냥 넘어갔을 것이다.
      3. 그러므로 memo[i-1] < num <= memo[i]인 곳을 찾아 memo[i] = num을 갱신해준다.
3. 최종적으로 탐색을 진행하면서 num에 따라 해당 조건을 넣어주면 된다.

if(num> lastNum){
	memo[len+1]= num;
}
if(memo[i-1] < num && num <= memo[i]){
	memo[i] = num;  
}​

 

처음에 어떻게 정렬되지도 않은 수열을 이진탐색으로 풀이한다고 했다면 이미 답이 나왔다. 위와 같은 풀이로 memo[] 1차원 배열에 조건에 맞춰 수를 탐색한다면 최종적으로 이 memo 배열은 오름차순으로 정렬된 상태로 유지된다.

 

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

 

DP를 통한 구현법은 2중 포문으로 시간복잡도가 O(N^2)이었는데,  이와 같은 이진탐색을 통한 최적화된 구현법은 원배열을 순회 O(N), 각 순회에서 이진 탐색 O(logN)으로 최종적으로 시간복잡도가 O(NlogN)가 된다.

 

풀이 코드 

// #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;
				System.out.println("길이 : " + len +" -> " +arr[i]);
				memo[len] = arr[i];
			}else {
//				idx = Arrays.binarySearch(memo, 0, len, arr[i]);
//				if(idx<0) {
//					idx = -idx-1;
//				}
				
				idx = binarySearch(0,len, arr[i]);
				System.out.println(arr[i] +" -> "+idx);
				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;
		
	}
}
	

 

☛ Arrays.binarySearch 사용할 때 주의할 점

 private static int binarySearch0(int[] a, int fromIndex, int toIndex,
                                     int key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            int midVal = a[mid];

            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found.
    }

 

while문을 보면 low<=high일 때만 실행된다. 그래서 key가 찾는 index가 fromIndex나 toIndex (한마디로 0이나 len 처럼 처음이나 끝 인덱스)일 경우 -(low+1)을 리턴한다. 그래서 아래처럼 예외처리를 해줘야한다.

→ 일반적인 이진탐색을 할 때는 상관없지만 지금은 arr을 탐색 후 memo라는 배열에 값을 넣는 과정이 있기 때문에 이러한 충돌이 발생한다.

반례
7
7 2 9 10 3 8 10
정답 : 4

원래 2(arr[1])의 index 1을 반환해야 하는데 -2 출력

 

idx = Arrays.binarySearch(memo, 0, len, arr[i]);
if (idx <0) idx= -idx-1;

---

❈ 출처

shoark7.github.io/programming/algorithm/3-LIS-algorithms#2