[백준] 400 - 다이나믹 프로그래밍 1 : 가장 긴 증가하는 부분 수열 (!) (11053번 JAVA)
최장 증가 부분 수열 이란...?
(LIS : Longest Increasing Subsequence)
: 어떤 임의의 수열이 주어질 때, 이 수열에서 볓개의 수들을 제거해서 부분수열을 만들 수 있다.
이때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라 한다.
cf) 동적 계획법으로 해결하는 유명한 알고리즘 문제 (알아놓자!)
[접근 방법]
1. O(N^2) 의 시간복잡도를 가지는 방법
★ 배열 10 20 10 30 20 50이 주어진 경우
index = 0은 원소 10이 자리하고 있다. 10 하나만 존재 하므로,
이때, LIS의 길이는 1 이다.
index = 1은 원소 20이 자리하고 있다. 이 경우 앞선 인덱스에 존재한 모든 원소보다 큼으로,
어느 경우에도 20을 마지막으로 하여 부분 증가 수열을 만들 수 있다.
따라서 가장 큰 LIS의 길이인 1에 +1을 하여,
이때, LIS의 길이는 2 이다.
이와 같은 방식으로 "LIS의 길이" 부분을 채워 가면 된다.
즉, 이전의 원소들을 탐색하며, 자신보다 작은 원소 중 가장 큰 "LIS의 길이" 값에 +1을 한다.
(여기서 "LIS의 길이"의 최소 값은 1이다. => 본인 보다 작은 원소가 없다면 1이다.)
하나의 예를 더 들어보자.
★ 배열 24 32 19 14 27 56 72 66 94 40 이 주어진 경우
현재 INDEX = 4를 탐색하고 있다.
원소는 27이다. 27 보다 작은 수는
INDEX = 0 의 원소 24,
INDEX = 2 의 원소 19,
INDEX = 3 의 원소 14 가 있다.
이 중 가장 큰 "LIS의 길이" 를 가지고 있는 것은
INDEX = 0 의 원소 24, INDEX = 2 의 원소 19, INDEX = 3 의 원소 14가 모두 1을 갖으므로,
INDEX = 4 의 원소 27은 "LIS의 길이"로 2을 갖는다.
완성된 표
[JAVA 코드 - Top - Down 방식]
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;
public class Main{
public static int[] arr;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// 1 <= N <= 1000
int N = Integer.parseInt(br.readLine());
arr = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=0; i<N; i++){
arr[i] = Integer.parseInt(st.nextToken());
}
bw.write(LIS(arr)+"\n");
bw.flush();
bw.close();
}
public static int LIS(int[] arr){
// LIS의 길이 저장
int[] D = new int[arr.length];
int result = 0;
for(int i=0; i<arr.length; i++){
D[i] = 1;
// INDEX = i 이전의 값 탐색
for(int j=0; j<=i; j++){
// 현재 원소보다 작음 and 현재 LIS의 길이 보다 큼 => 갱신
if (arr[i] > arr[j] && D[j] + 1 > D[i]){
D[i] = D[j] + 1;
}
}
if(D[i] > result){
result = D[i];
}
}
return result;
}
}
[JAVA 코드 - Botton - Up 방식]
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// 수열 A의 크기 N (1 ≤ N ≤ 1,000)
int N = Integer.parseInt(br.readLine());
int[] A = new int[N+1];
int[] DP = new int[N+1];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i=1; i<N+1; i++) {
A[i] = Integer.parseInt(st.nextToken());
}
for(int i=1; i<=N; i++){
DP[i] = 1;
for(int j=1; j<i; j++){
if(A[j] < A[i] && DP[i] < DP[j] + 1){
DP[i] = DP[j] + 1;
}
}
}
// 가장 긴 증가하는 부분 수열 길이 구하기
// 삼항 연산자 활용
int max_length = -1;
for(int i=1; i<=N; i++){
max_length = DP[i] > max_length ? DP[i] : max_length;
}
bw.write(max_length + "\n");
bw.flush();
bw.close();
}
}
'백준 > DP' 카테고리의 다른 글
[백준] 연속합 (1912번 JAVA) (!) / 400 - 다이나믹 프로그래밍 1 (1) | 2023.01.16 |
---|---|
[백준] 가장 긴 증가하는 부분 수열 4 (14002번 JAVA) / 400 - 다이나믹 프로그래밍 1 (0) | 2023.01.16 |
[백준] 다이나믹 프로그래밍(DP) - "1, 2, 3 더하기" 시리즈 (0) | 2023.01.15 |
[백준] 1, 2, 3 더하기 9 (16195번 JAVA) (0) | 2023.01.15 |
[백준] 1, 2, 3 더하기 8 (15993번 JAVA) (0) | 2023.01.15 |