[코테]16-가장 긴 증가하는 부분 수열

가장 긴 증가하는 부분 수열(11053)

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제.
LIS라고도 함.
부분 수열 ? 수열 수를 선택해서 만드는 수열.
수열에 있던 수의 순서는 변경할 수 없음.

• 수열 A의 길이 : N, 가능한 부분 수열은 2^N가지

• 연속을 처리하기 위해서는 마지막 수가 무엇인지가 중요했음.
  D[i][j] -> i는 길이, j는 마지막 수였음.

• 이미 있는 수를 이용하기 때문에 1차원으로 풀 수 있음.
  어떤 수가 와야하는지 모르는 것이 아니기 때문에, j는 필요없음.

• D[i] = A[1], ....A[i]까지 수열이 있을 때, A[i]를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이.

• D[i]는 A[i]가 반드시 포함되어야 한다.

• 가장 긴 부분의 수열이 A[?],A[?], ... ,A[j], A[i]라고 했을 때 겹치는 부분 문제를 찾아보자.

• D[i] = A[1] ~ A[i], A[i]를 마지막으로 하는 LIS의 길이.

D[i]=max(D[j])+1 (j<i, A[j]<A[i])

• 시간복잡도.
  문제의 개수 = N.
  문제 1개를 푸는데 걸리는 시간 = N
  O(N^2)

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n= sc.nextInt();
		int a[]= new int[n];
		for(int i=0;i<n;i++) {
			a[i]=sc.nextInt();
		}
		int d[]=new int[n];
		
		for(int i=0;i<n;i++) {
			d[i]=1;
			for(int j=0;j<i;j++){
				if(a[j] < a[i] && d[i] < d[j]+1) {
					d[i] = d[j]+1;
				}
			}
		}
		int res =d[0];
		for(int i=0;i<n;i++) {
			res = Math.max(d[i], res);
		}
		System.out.println(res);
	}
}

가장 긴 증가하는 부분 수열 4

LIS 길이를 구하는데, 그 때 LIS는 무엇인지까지 출력해야함.
V[i] = A[i]의 앞에 와야 하는 수의 인덱스, 즉 A[i]의 앞에는 A[V[i]]가 와야 길이가 가장 길다.

• 역추적해나가면서 풀면 된다.

import java.util.*;

public class Main {
	static int a[];
	static int d[];
	static int v[];
	
	static void go(int p) {
		if(p==-1) return;
		go(v[p]);
		System.out.println(a[p]+" ");
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n= sc.nextInt();
		a = new int[n];
		for(int i=0;i<n;i++) {
			a[i]=sc.nextInt();
		}
		d=new int[n];
		v=new int[n];
		
		for(int i=0;i<n;i++) {
			d[i]=1;
			v[i]=-1;
			for(int j=0;j<i;j++){
				if(a[j] < a[i] && d[i] < d[j]+1) {
					d[i] = d[j]+1;
					v[i]=j;
				}
			}
		}
		
		int res =d[0];
		int p=0;
		for(int i=0;i<n;i++) {
			if(res < d[i]) {
				res = d[i];
				p = i;
			}
		}
		System.out.println(res);
		go(p);
		System.out.println();
	}
}

연속합(1912)

n개의 정수로 이루어진 임의의 수열이 주어진다.
우리는 이 중 연속된 몇 개의 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다.
단, 숫자는 한 개 이상 선택해야 한다.

• 이 문제의 입력은 음수,양수,0도 가능함.
  가장 큰 합을 구하려면 양수가 필요함. 그렇다고 음수를 빼고 계산하면 안됨.
  -1이 포함되었지만 3,-1,3 이렇게 되면 정답이 될 수도 있음.

• D[i] = i번째 수로 끝나는 가장 큰 연속합.
  이렇게 식을 구했으면, i번째 수에게 가능한 경우를 세야한다.

• 정답 : D[1],,,,D[N]중 최대값.

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n= sc.nextInt();
		int a[]=new int[n];
		for(int i=0;i<n;i++) {
			a[i]=sc.nextInt();
		}
		
		int d[]=new int[n];
		for(int i=0;i<n;i++) {
			d[i] = a[i];
			if(i==0) {
				continue;
			}
			if(d[i] < d[i-1] + a[i]) {
				d[i] = d[i-1] + a[i];
			}
		}
		int res = d[0];
		for(int i=0;i<n;i++) {
			res = Math.max(res, d[i]);
		}
		System.out.println(res);
	}
}

최백준 선생님의 코딩테스트 기초 강의를 보고 작성한 글입니다.