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

백준 문제 풀다가 LIS 문제가 나왔는데 구글의 도움을 받고 풀어서 ㅠㅠ 정리해보려고 한다🤗

 

 

 

 

 

 

 

 

🔍 최장 증가 부분 수열 (LIS)

• 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 찾는 문제
• 이 때 부분 수열은 연속적이거나, 유일할 필요는 없다

 

 

 

 

 

 

 

🔍 구현 방법

총 2가지 방식으로 구현할 수 있다.

 

• 동적 계획법을 활용한 풀이 → O(N^2)
• 이분 탐색을 활용한 풀이 → O(NlogN)

 

이 문제를 두가지 방식으로 해결해봅시다❕

https://www.acmicpc.net/problem/11053

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

 

 

 

 

 

1️⃣ 동적 계획법을 활용한 풀이

public class LIS1 {
	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();
	}
}

 

 

 

 

 

 

2️⃣ 이분 탐색을 활용한 풀이

public class LIS2 {
	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;
		}
	}
}

 

 

 

 

 

 

 

 

 

 

🔍 최장 증가 부분 수열 문제

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

https://www.acmicpc.net/problem/11053

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

 

 

백준 11054 가장 긴 바이토닉 부분 수열 - G4

https://www.acmicpc.net/problem/11054

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

 

 

백준 2631 줄세우기 - G4

https://www.acmicpc.net/problem/2631

2631번: 줄세우기