이번에는 연관된 수열 문제 3개를 한꺼번에 풀어보았다.
아래는 백준 기초 알고리즘 1/2 시리즈에 나오는 수열들이다.
1. 증가하는 수열 (11055)
2. 감소하는 수열 (11722)
3. 바이토닉 수열 (11054)
11055 - 가장 큰 증가하는 부분 수열
문제 링크
https://www.acmicpc.net/problem/11055
증가하는 부분 수열 중에서 합이 가장 큰 것을 구한다.
- dp[i]를 현재 input[i]로 초기화한다.
- input[i]와 input[j]를 비교해서 더 크고 + (input[i] + dp[j])가 dp[i]보다 더 큰 경우에 dp[i]를 갱신한다.
최종적으로 for문으로 가장 큰 값을 구하면 된다. 아래 코드를 반복해서 쓴다.
int max = 0;
for(int i = 0; i < N; i++) {
max = Math.max(max, 비교할 값)
}코드
import java.io.BufferedReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new java.io.InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] dp = new int[N+1];
int[] input = new int[N+1];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
input[i] = Integer.parseInt(st.nextToken());
dp[i] = input[i];
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j < i; j++) {
if(input[j] < input[i]) {
dp[i] = Math.max(dp[i], dp[j] + input[i]);
}
}
}
int max = Integer.MIN_VALUE;
for (int i : dp) {
max = Math.max(i, max);
}
System.out.println(max);
}
}11722 - 가장 긴 감소하는 부분 수열
문제 링크
https://www.acmicpc.net/problem/11722
이 문제는 가장 긴 감소하는 부분 수열의 개수(count)를 구하는 것이다.
이전 증가하는 수열과 90% 일치한다.
- i과 j들을 비교해서 i가 더 작은 경우
- dp[j] + 1 한 값이 dp[i]보다 더 클 경우
본인과 본인 앞의 수들을 계속 비교해가면서 현재의 dp값을 갱신시키고
최종적으로 가장 큰 값을 출력한다. (증가 수열과 동일)
가장 큰 증가 수열과 다른 점은 dp[i] 초기값이 input[i]가 아니라 1부터 시작한다는 점이겠다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new java.io.InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] input = new int[N];
int[] dp = new int[N];
for(int i = 0; i < N; i++) {
// st로
input[i] = Integer.parseInt(st.nextToken());
}
for(int i = 0; i < N; i++) {
// 일단 기본으로 dp[i]에 1 넣고 들어가! 최소 수열의 길이는 1이기 때문이다.
dp[i] = 1;
for(int j =0; j < i; j++) {
/**
* 내가 i, 내 이전 애들이 j라고 했을때,
* input[i]가 input[j]보다 작고 + (dp[j] + 1)이 dp[i]보다 크다면
* dp[i] = dp[j] + 1
*/
if (input[i] < input[j] && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
}
}
}
int length = 0;
for(int i = 0; i < N; i++) {
length = Math.max(length, dp[i]);
}
System.out.println(length);
}
}11054 - 가장 긴 바이토닉 부분 수열
문제 링크
https://www.acmicpc.net/problem/11054
바이토닉은 LIS를 왼-오, 오-왼 방향으로 진행한 버전이라고 할 수 있다.
11055번이 LIS였다.
LIS: 최장 증가 부분 수열 알고리즘
가장 쉬운 그림 설명이 있다. (출처: https://st-lab.tistory.com/136)
두 dp 배열을 합쳐서 -1한다. 끝.
-1을 왜 할까? 우리가 부분 수열 count를 셀 때 최솟값으로 1을 설정하는데,
왼쪽에서 시작하고, 오른쪽에서 시작하고 합치면 같은 수인데 1이 두 번 들어가기 때문에 계산을 다 하고 나서 -1 해주는 것이다.
주의점
나의 경우는 착각해서 최장 증가 수열이랑 최장 감소 수열을 dp로 구해서 합치는 바람에 틀렸다.
최장 증가 수열을 왼쪽~오른쪽, 오른쪽~왼쪽으로 진행해야 한다는 것!
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new java.io.InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
int[] r_dp = new int[N];
int[] l_dp = new int[N];
int[] input = new int[N];
for(int i = 0; i < N; i++) {
input[i] = Integer.parseInt(st.nextToken());
}
for(int i = 0; i < N; i++) {
r_dp[i] = 1;
for(int j = 0; j < i; j++) {
if(input[j] < input[i] && r_dp[i] < r_dp[j] + 1) {
r_dp[i] = r_dp[j] + 1;
}
}
} // 여기까지는 기존의 증가하는 수열 로직과 같다.
for(int i = N - 1; i >= 0; i--) {
l_dp[i] = 1; // 초기값은 1로 설정해야 한다.
for(int j = N -1; j > i; j--) {
if(input[i] > input[j] && l_dp[i] < l_dp[j] + 1) {
l_dp[i] = l_dp[j] + 1;
}
}
}
// LIS를 왼->오, 오->왼 2가지 방향에서 각각 구한 다음에 합쳐야 하는 것이었다.
int max = 0;
for(int i = 0; i < N; i++) {
if (max < r_dp[i] + l_dp[i]) {
max = r_dp[i] + l_dp[i];
}
}
System.out.println(max - 1); // 최종적으로 숫자 1만 중복된다. 그냥 최후에 1번 빼면 된다.
}
}보다시피 if 조건식이 LIS 그대로다.
다만 오른쪽에서부터 시작하는 LIS는 반대로 i가 j보다 작을 때여야 한다는거
후기
같은 시리즈를 모아푸니 이해를 더 높일 수 있었다.
바이토닉의 경우 개념 자체가 어려웠어서 다시 볼 예정이다.
