[SWEA] 3307:최장 증가 부분 수열 (Java 자바)

풀이 및 소스코드

 

LIS(Longest increasing Subsequence)란, 가장 긴 증가하는 부분 수열이다.

 

예를 들어,

[6, 2, 5, 1, 7, 4, 8, 3] 이라는 배열이 있을 경우, LIS는 [2, 5, 7, 8]이 된다.

증가하는 부분 수열 중 가장 긴 것이기 때문.

 

 

LIS를 풀기 위한 가장 일반적인 방법은 DP를 이용하는 것이다.

[100, 50, 70, 90, 75, 87, 105, 78, 110, 60] 이 배열의 LIS를 구한다고 가정해보면,

LIS는 [50, 70, 75, 87, 105, 110] 로, 길이는 6이 된다.

아래와 같은 순서로 진행된다.

[0] 
[0, 100]
[0, 50]
[0, 50, 70]
[0, 50, 70, 90]
[0, 50, 70, 75]
[0, 50, 70, 75, 87]
[0, 50, 70, 75, 87, 105]
[0, 50, 70, 75, 78, 105]

[0, 50, 70, 75, 78, 105, 110]
[0, 50, 60, 75, 78, 105, 110]

0을 뺀 나머지의 길이를 구하면 LIS의 길이가 된다.

 

이분탐색으로 구한 LIS와 실제 LIS의 값들이 다른 것을 주의깊게 봐야한다.

수열상에서 뒤에 있던 원소가 먼저 들어온 원소보다 lower_bound로 탐색된 최적의 위치가 앞에 있을 수도 있기 때문입니다.

따라서 배열에 들어있는 값들은 LIS를 이루는 요소와 무관하다는 것이다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Solution {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();

		int t = Integer.parseInt(br.readLine());

		for (int tt = 1; tt <= t; tt++) {
			int n = Integer.parseInt(br.readLine());
			st = new StringTokenizer(br.readLine());
			LinkedList<Integer> list = new LinkedList<>();
			list.add(-1);
			for (int i = 0; i < n; i++) {
				int a = Integer.parseInt(st.nextToken());
				if (a >= list.get(list.size() - 1)) {
					list.add(a);
					continue;
				}

				int start = 0;
				int end = list.size();
				int mid = 0;

				while (start < end) {
					mid = (start + end) / 2;

					if (a > list.get(mid)) {
						start = mid+1;
					} else {
						end = mid;
					}
				}

				list.remove(end);
				list.add(end, a);
			}
			sb.append("#").append(tt).append(" ").append(list.size() - 1).append("\n");
		}
		System.out.println(sb);

	}

}

 

 

 

https://jainn.tistory.com/90

최장 증가 부분 수열(LIS) 알고리즘