LIS 최장 증가 수열

입력한 수열에서 순차적으로 증가하는 수열을 추출하여 그 수열의 길이를 출력하는 알고리즘 문제이다.

 

1. 단순한 방법

해당 문제에서 단순한 방법은 모든 경우의 수열을 도출하여 그 수열의 길이를 비교하여 최대 길이의 수열을 알아내는 것이다. 이 방법은 입력하는 수열의 길이에 따라서 부분 수열이 기하급수적으로 증가하기 때문에 해당 문제에서 통과하기 어려운 방법이다.

 

2. DP를 활용한 방법

n번째 수열의 숫자가 n+1번째 수열의 숫자보다 크다면 n+1번째까지의 수열에서의 최장 증가 수열은 n번째 수열의 최장 증가 수열에서 1을 더한 값을 길이로 가진다.

n번째 수열의 숫자가 n+1번째 수열의 숫자보다 작다면 n+1번째까지의 수열에서의 최장 증가 수열은 n-1에서 1위치의 숫자가 마지막인 수열이고 n번째 수를 더할 수 있는 것이며 가장 긴 수열에서 1을 더한 값을 길이로 가진다.

이 과정을 반복하여 최대값을 구하여 출력하는 방법이다.

import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		//가장 쉬운 방법 모든 경우의 수를 검사하여 증가하는 수열인지 판별한다.
		/*
		효율적인 방법 다이나믹 프로그래밍 기법 사용
		입력한 수열의 길이만큼 배열을 선언한다.
		이 배열 i번째에는 i를 포함한 최장 공통 수열의 길이를 저장하고 있다.
		*/
		int result = 1;
		int data_len = Integer.parseInt(br.readLine());
		int data[] = new int[data_len];
		int input_int[] = new int[data_len];
		String [] input = br.readLine().split(" ");
		for(int i = 0; i< data_len; i++) {
			input_int[i] = Integer.parseInt(input[i]);
		}
		//
		for(int i = 0; i< data_len ; i++) {
			data[i] = 1;
			for(int j = i-1; j >= 0 ; j--) {
				if(input_int[j] < input_int[i]) {
					data[i] = Math.max(data[j]+1, data[i]);
				}
			}
		}
		for(int x : data) {
			result = Math.max(x, result);
		}
		//
		bw.write(result+"");
		bw.flush();
		br.close();
		bw.close();		
	}
}

3. 분할 정복 적용

수열을 저장할 데이터 공간에 입력받은 수열의 데이터를 입력하는 방식으로 최장 증가 수열의 길이를 알 수 있다. 입력받은 수열에서 순서대로 숫자를 데이터 공간에 입력한다. 이때 숫자의 수와 입력된 데이터들을 고려하여 위치를 특정한다는 것이 앞선 방법과의 차이점이다.

import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int result = 1;
		int data_len = Integer.parseInt(br.readLine());
		Vector<Integer> data = new Vector<Integer>();
		int input_int[] = new int[data_len];
		String [] input = br.readLine().split(" ");
		for(int i = 0; i< data_len; i++) {
			input_int[i] = Integer.parseInt(input[i]);
		}
		//
		data.add(0);
		for(int num : input_int) {
			if(data.lastElement() < num) {
				data.add(num);
			}
			else {
				int index = Collections.binarySearch(data, num);				
				data.set(index < 0 ? -(index+1) : index, num);
			}
		}
		result = data.size()-1;
		//
		bw.write(result+"");
		bw.flush();
		br.close();
		bw.close();		
	}
}

 

출처 : https://www.acmicpc.net/problem/12015

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