[코테]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);
}
}
최백준 선생님의 코딩테스트 기초 강의를 보고 작성한 글입니다.
Author And Source
이 문제에 관하여([코테]16-가장 긴 증가하는 부분 수열), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@tms01365/코테16-가장-긴-증가하는-부분-수열저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)