[Algorithm] LIS (최장 증가 부분 수열)

ONE·2022년 5월 16일
0

Algorithm

목록 보기
5/5

최장 증가 부분 수열 (Longest Increasing Subsequence)

  • 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라 한다
    • 예를 들어, { 6, 2, 5, 1, 7, 4, 8, 3} 이라는 배열이 있을 경우, LIS는 { 2, 5, 7, 8 }
  • 일반적으로 최장 증가 부분 수여르이 길이를 구하는 방법은 DP를 이용하는 것
import java.util.Scanner;

public class LIS_DP1 {
	static int N;
	static int[] arr;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		arr = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = sc.nextInt();
		}

		// 각 위치에서의 LIS를 저장할 1차원 dp 테이블을 정의한다.
		int[] dp = new int[N];
		// 최대 LIS의 값.
		int max = 1;

		// 첫 번째 원소부터 N번째 원소까지 dp 테이블의 값을 채워 나간다.
		for (int i = 0; i < N; i++) {
			// 우선 해당 위치를 본인의 길이(1)로 초기화한다.
			dp[i] = 1;
			// 현재 원소의 위치에 대하여, 앞의 원소의 값을 비교하며 값을 갱신한다.
			for (int j = 0; j < i; j++) {
				// 만일 부분 수열이 증가할 가능성이 있다면
				if (arr[j] < arr[i]) {
					// dp 테이블에 저장된 LIS를 바탕으로 가장 큰 값을 dp[i]의 값으로 갱신한다.
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}
			}

			// 전체 수열에서 LIS의 값을 갱신한다.
			max = Math.max(max, dp[i]);
		}

		System.out.println(max);
		sc.close();
	}
}

위의 코드로 구현하게되면 시간복잡도가 O(N²) 이 되는데 이를 이분탐색을 활용하여 구햔하게 되면 O(NlogN) 의 시간복잡도로 구현할 수 있게 된다

  • LIS의 형태를 유지하기 위해 주어진 배열의 인덱스를 하나씩 살펴본다
  • 해당 숫자가 들어갈 위치를 이분탐색으로 탐색해 삽입

import java.util.Scanner;

public class LIS_DP2 {
	static int N;
	static int[] arr, dp;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		arr = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = sc.nextInt();
		}

		// dp에 실질적으로 저장된 원소의 길이 = LIS인 1차원 dp테이블을 만든다.
		// 해당 dp에 저장된 원소(0이 아닌 값)들은 이후 조사하는 원소들이 부분 수열을 늘릴 수 있을지에 대한 정보를 제공한다.
		dp = new int[N];
		// 처음에 저장된 원소는 없으므로, LIS = 0이다.
		int LIS = 0;

		// 첫 번째 원소부터 N번째 원소까지 dp 테이블의 값을 채워 나간다.
		for (int i = 0; i < N; i++) {
			// 이분 탐색을 활용하여 dp테이블에 저장된 원소를 탐색하며 현재 선택된 숫자가 dp테이블의 어떤 위치에 포함될지 파악한다.
			int idx = BinarySearch(arr[i], 0, LIS, LIS + 1);
			
			// 찾지 못한 경우
			if(idx == -1) {
				// 가장 마지막 위치에 원소를 삽입하고 LIS의 길이를 늘린다.
				dp[LIS++] = arr[i];
			}
			// 찾은 경우
			else {
				// 해당 위치에 현재 값을 삽입하여 갱신한다.
				dp[idx] = arr[i];
			}
		}
		
		// LIS의 길이를 출력한다.
		System.out.println(LIS);

		sc.close();
	}

	private static int BinarySearch(int num, int start, int end, int size) {
		int res = 0;
		while (start <= end) {
			// 중앙 값을 찾는다.
			int mid = (start + end) / 2;

			// 만일 현재 선택된 원소가 해당 원소보다 작거나 같다면, 앞 부분을 탐색한다.
			if (num <= dp[mid]) {
				// 해당 원소의 위치를 기억해둔다.
				res = mid;
				end = mid - 1;
			}
			// 만일 현재 선택된 원소가 해당 원소보다 크다면, 뒷 부분을 탐색한다.
			else {
				start = mid + 1;
			}
		}

		// dp테이블에서 삽입될 위치를 찾지 못한 경우(즉, 모든 수들보다 큰 경우).
		if (start == size) {
			return -1;
		}
		// dp테이블에서 삽입될 위치를 찾은 경우.
		else {
			return res;
		}
	}
}
  • 해당 방법을 이용하면 최장 증가 부분 수열의 길이는 확실하게 알 수 있지만, 새로 만들어진 배열이 무조건 LIS 가 만들어지는 것은 아니라서 추가적인 작업을 해줘야 한다

출처

profile
New, Strange, Want to try

0개의 댓글