[Algorithm] 최장 증가 부분 수열(LIS) 알고리즘 (JAVA로 구현)

 

🚀

 

📖 최장 증가 부분 수열 (Longest Increasing Subsequence)이란?

어떤 수열이 주어질 때 그 수열에서 몇 개의 수들을 제거하여 부분 수열을 만들 수 있는데 그중에서 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열(LIS)라고 합니다. 동적 계획법(DP)으로 풀이할 수 있습니다.

 

위와 같은 수열이 있다고 가정할 때 우리는 눈대중으로 봐도 가장 긴 증가 부분 수열을 알 수 있습니다.

 

하지만 이를 코드로 구현한다면 생각을 좀 해봐야 할 것 같습니다.

 

💡 핵심 아이디어 (이중 for문 / 시간 복잡도 O(N²))

dp[i] : i번째 수를 마지막 원소로 가지는 LIS의 길이

 i번째 원소를 i-1번째 원소와 비교했을 때 0~i-1번째 원소들 중에서 i번째 원소보다 작은 원소들의 dp값들 중 가장 큰 값 + 1을 dp[i]로 기록한다.

 

아래의 배열을 예시로 들어보겠습니다.

첫 시작은 1로 시작합니다.

 

현재 값은 6이고 6보다 작은 이전 원소들 중 가장 큰 dp값이 1이므로 1+1 = 2를 현재 dp값으로 기록합니다.

 

현재 값은 3이고 3보다 작은 이전 원소들 중 가장 큰 dp값이 1이므로 1+1 = 2를 현재 dp값으로 기록합니다.

 

현재 값은 4고 4보다 작은 이전 원소들 중 가장 큰 dp값이 2이므로 2+1 = 3을 현재 dp값으로 기록합니다.

 

현재 값은 2이고 2보다 작은 이전 원소들 중 가장 큰 dp값이 1이므로 1+1 = 2를 현재 dp값으로 기록합니다.

 

현재 값은 7이고 7보다 작은 이전 원소들 중 가장 큰 dp값이 3이므로 3+1 = 4를 현재 dp값으로 기록합니다.

 

현재 값은 8이고 8보다 작은 이전 원소들 중 가장 큰 dp값이 4이므로 4+1 = 5를 현재 dp값으로 기록합니다.

 

현재 값은 5이고 5보다 작은 이전 원소들 중 가장 큰 dp값이 3이므로 3+1 = 4를 현재 dp값으로 기록합니다.

 

📋 코드

import java.util.*;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int arr[] = { 1, 6, 3, 4, 2, 7, 8, 5 };
		int dp[] = new int[8];

		dp[0] = 1;
		for (int i = 1; i < 8; i++) {
			int tmp = 1;
			for (int j = 0; j < i; j++) {
				if(arr[j] < arr[i]) {
					tmp = Math.max(tmp, dp[j]);
				}
				dp[i] = tmp+1;
			}
		}
		
		for (int i = 0; i < 8; i++) {
			System.out.print(arr[i]+" ");
		}
		System.out.println();
		for (int i = 0; i < 8; i++) {
			System.out.print(dp[i]+" ");
		}
	}
}

👨🏻‍💻 결과

 

 

✏️ 또 다른 풀이 2 (이분 탐색 / 시간 복잡도 O(NlogN))

dp를 사용한 방법은 구현이 쉽지만 시간 복잡도가 O(N²)이므로 N 커질수록 효율이 떨어지게 되지만, 이분 탐색인 lower_bound를 이용하면 시간 복잡도를 O(NlogN)까지 줄일 수 있습니다.

이분 탐색 방법은 수열 LIS를 만들어 놓고 하나씩 채워나가면서 LIS를 유지하기 위한 최적의 위치에 수를 삽입하는 방식인데 ㅇ아래의 예시로 설명드리겠습니다.

 

첫 값은 첫자리에 놓습니다.

 

오름차순이니 다음 순서에 수를 놓습니다.

 

이분 탐색으로 처음으로 3보다 커지는 자리에 3을 놓습니다.

 

오름차순이니 다음 순서에 수를 놓습니다.

 

이분 탐색으로 처음으로 2보다 커지는 자리에 2를 놓습니다.

 

오름차순이니 다음 순서에 수를 놓습니다.

 

오름차순이니 다음 순서에 수를 놓습니다.

 

이분 탐색으로 처음으로 5보다 커지는 자리에 5를 놓습니다.

 

 

📋 코드

import java.util.*;

public class Main {
	
	public static int lowerBound(int[] array,  int value, int s, int e) {
        while (s < e) {
            int mid = s + (e - s)/2;
            if (value <= array[mid]) {
                e = mid;
            } else {
                s = mid + 1;
            }
        }
        return s;
    }

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int arr[] = { 1, 6, 3, 4, 2, 7, 8, 5 };
		int LIS[] = new int[8];

		int cnt = 0;
		LIS[cnt++] = arr[0];
		for (int i = 1; i < 8; i++) {
			if(LIS[cnt-1] < arr[i]) {
				LIS[cnt++] = arr[i];
			}else {
				int idx = lowerBound(LIS, arr[i], 0, cnt);
				LIS[idx] = arr[i];
			}
		}
		
		for (int i = 0; i < 8; i++) {
			System.out.print(arr[i]+" ");
		}
		System.out.println();
		for (int i = 0; i < 8; i++) {
			System.out.print(LIS[i]+" ");
		}
		
	}
}

👨🏻‍💻 결과

 

이분 탐색의 경우 정확한 LIS가 아닌 LIS 길이를 구할 때 사용됩니다.

 

 

 

 

🧩 예제 문제

https://cocoon1787.tistory.com/701

[JAVA] 백준 11053번 - 가장 긴 증가하는 부분 수열

https://cocoon1787.tistory.com/702

[JAVA] 백준 11054번 - 가장 긴 바이토닉 부분 수열