[백준] 11054번 : 가장 긴 바이토닉 부분 수열 - JAVA [자바]
11054번: 가장 긴 바이토닉 부분 수열
첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)
www.acmicpc.net
- 문제
이전 문제인 가장 긴 증가하는 부분 수열을 풀어보셨다면 매우 쉽게 풀 수 있는 문제다. 이 문제를 풀기 전에 앞서 아래 포스팅을 보고 오는 걸 추천드린다.
[백준] 11053번 : 가장 긴 증가하는 부분 수열 - JAVA [자바]
www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인..
st-lab.tistory.com
- 알고리즘 [접근 방법]
문제 예제를 한 번 보도록하자.
일단 이전 포스팅에서는 LIS(최장 증가 부분수열)에 대해 알아보았다. 이번에는 개념 하나가 더 추가 되는데, 증가가 있다면 감소도 있듯 이러한 부분 감소 수열을 LDS(최장 감소 부분수열)이라 한다. LDS자체 알고리즘은 LIS을 역으로 탐색하면 되기 때문에 별도로 알고리즘 설명을 하지는 않겠다.
먼저 바이토닉(Bitonic)에 대해 정의를 알아보자. 바이토닉의 경우 특정 값을 기준으로 왼쪽 부분은 오름차순, 오른쪽 부분은 내림차순인 수열 또는 그러한 부분 순환이동을 말한다..
위의 개념을 적용한 것중 가장 유명한 것이 바이토닉 정렬(Bitonic sort)이지 않을까 싶다. (나중에 기회되면 다뤄보도록..) 특히 이제 시대는 단일스레드가 아닌 멀티스레드가 대세이기 때문에 병렬 정렬 알고리즘도 많이 쓰이고, 여기서 시간복잡도가 O(log2N)으로 다른 일반적인 직렬 정렬의 한계인 O(NlogN)에 비해 엄청 빠르다. 대강 이정도 차이..
(분홍색이 log2N, 파랑색이 NlogN이다)
여튼 본격적으로 바이토닉 수열이 어떤 것을 의미하는지는 알겠으니 알고리즘을 보자
주어진 수열은 {1, 5, 2, 1, 4, 3, 4, 5, 2, 1} 이고, 오름차순이거나(LIS), 내림차순이거나(LDS), 한 번 올랐다가 내림차순으로 진행 하는 것 중 가장 긴 부분수열을 구하면 된다. 그럼 가장 문제인 '올라갔다가 내려가는 부분수열'을 어떻게 구해야 하는지다.
일단, 오름차순 부분수열, 즉 왼쪽에서 오른쪽으로 진행하는 오름차순의 경우 각 원소별 수열의 길이를 보면 다음과 같다.
r_dp의 각 원소를 좀 더 구체적으로 설명하자면 다음과 같다.
r_dp[0] = {1} : 길이 1
r_dp[1] = {1, 5} : 길이 2
r_dp[2] = {1, 2} : 길이 2
r_dp[3] = {1} : 길이 1
r_dp[4] = {1, 2, 4} : 길이 3
r_dp[5] = {1, 2, 3} : 길이 3
r_dp[6] = {1, 2, 3, 4} : 길이 4
r_dp[7] = {1, 2, 3, 4, 5} : 길이 5
r_dp[8] = {1, 2} : 길이 2
r_dp[9] = {1} : 길이 1
그리고 내림차순 부분수열의 경우 거꾸로 생각하여 오른쪽에서 왼쪽으로 진행하는 오름차순 부분수열이랑 같은 의미다. 그리고 각 부분수열에 대한 길이는 다음과 같이 구할 수 있다.
[역방향]
l_dp[9] = {1} : 길이 1
l_dp[8] = {1, 2} : 길이 2
l_dp[7] = {1, 2, 5} : 길이 3
l_dp[6] = {1, 2, 4} : 길이 3
l_dp[5] = {1, 2, 3} : 길이 3
l_dp[4] = {1, 2, 3, 4} : 길이 4
l_dp[3] = {1} : 길이 1
l_dp[2] = {1, 2} : 길이 2
l_dp[1] = {1, 2, 3, 4, 5} : 길이 5
l_dp[0] = {1} : 길이 1
이제 여기서 가장 긴 부분수열을 구할 수 있다. 어떻게하냐? 바로 우리가 구한 두 수열을 합치는 것이다.
즉, 각각의 수열을 합침으로인해 오름차순과 내림차순이 합쳐진 수열이 완성되는 것이다.
다만 주의할 것이 result 배열은 단순히 합친 것이므로 원소 1개씩 중복되어 있다는 점이다. 그러므로 진짜 최종 결과는 -1 씩 해주어야 한다.
아래 배열이 진짜 최종 값일 것이다.
우리가 찾아야 할 것은 최장 길이 부분수열이므로 위의 배열에서 최댓값인 7이 정답이 되는 것이다.
실제 각 원소별 수열은 다음과 같다.
result[0] = (r_dp[0] + l_dp[0]) = {1} + {1} = {1} : 길이 1
result[1] = (r_dp[1] + l_dp[1]) = {1, 5} + {5, 4, 3, 2, 1} = {1, 5, 4, 3, 2, 1} : 길이 6
result[2] = (r_dp[2] + l_dp[2]) = {1, 2} + {2, 1} = {1, 2, 1} : 길이 3
result[3] = (r_dp[3] + l_dp[3]) = {1} + {1} = {1} : 길이 1
result[4] = (r_dp[4] + l_dp[4]) = {1, 2, 4} + {4, 3, 2, 1} = {1, 2, 4, 3, 2, 1} : 길이 6
result[5] = (r_dp[5] + l_dp[5]) = {1, 2, 3} + {3, 2, 1} = {1, 2, 3, 2, 1} : 길이 5
result[6] = (r_dp[6] + l_dp[6]) = {1, 2, 3, 4} + {4, 2, 1} = {1, 2, 3, 4, 2, 1} : 길이 6
result[7] = (r_dp[7] + l_dp[7]) = {1, 2, 3, 4, 5} + {5, 2, 1} = {1, 2, 3, 4, 5, 2, 1} : 길이 7
result[8] = (r_dp[8] + l_dp[8]) = {1, 2} + {2, 1} = {1, 2, 1} : 길이 3
result[9] = (r_dp[9] + l_dp[9]) = {1} + {1} = {1} : 길이 1
감이 오시는가?
그러면 이제 순방향(LIS)과 역방향(LDS)의 오름차순 부분수열을 구하면 되겠다.
위에서 필자가 보고 오라는 포스팅의 기본 Top-Down 알고리즘은 다음과 같았다.
static int LIS(int N) {
// 만약 탐색하지 않던 위치의 경우
if(dp[N] == null) {
dp[N] = 1; // 1로 초기화
// N 이전의 노드들을 탐색
for(int i = N - 1; i >= 0; i--) {
// 이전의 노드 중 seq[N]의 값보다 작은 걸 발견했을 경우
if(seq[i] < seq[N]) {
dp[N] = Math.max(dp[N], LIS(i) + 1);
}
}
}
return dp[N];
}
이게 가장 기본적인 LIS 구하는 방법이였다.
그러면 거꾸로 감소 부분수열인 LDS는 어떻게 구하면 되는가..? 바로 위 로직에서 반복문의 탐색부분만 바꿔주면 된다.
생각해보자. LIS의 경우 N에 대하여 N 이전의 노드들을 탐색하고 그 중 N의 노드 값보다 작은 값들에 대해 재귀호출을 했다. 그럼 반대로, N이후의 노드들을 탐색하면서 이후 노드들이 N의 노드값보다 작으면 되는거 아닌가?
즉, 아주 간단하게 탐색 방향만 바꿔주면 된다. 아래와 같이 말이다.
static int LDS(int N) {
// 만약 탐색하지 않던 위치의 경우
if (dp[N] == null) {
dp[N] = 1; // 1로 초기화
// N 이후의 노드들을 탐색
for (int i = N + 1; i < dp.length; i++) {
// 이후의 노드 중 seq[N]의 값보다 작은 걸 발견했을 경우
if (seq[i] < seq[N]) {
dp[N] = Math.max(dp[N], LDS(i) + 1);
}
}
}
return dp[N];
}
N 이전의 노드들이 아닌 N 이후의 노드들을 탐색하는 것만 바꿔주면 끝이다.
이렇게 두 알고리즘을 통해 탐색하며 각 탐색한 dp의 값끼리 합친 후 가장 큰 값을 찾아내면 된다.
Bottom-Up방식도 마찬가지다. 이 방식의 LIS 기본 알고리즘은 다음과 같았다.
for(int i = 0; i < N; i++) {
dp[i] = 1;
// 0 ~ i 이전 원소들 탐색
for(int j = 0; j < i; j++) {
// j번째 원소가 i번째 원소보다 작으면서 i번째 dp가 j번째 dp+1 값보다 작은경우
if(seq[j] < seq[i] && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1; // j번째 원소의 +1 값이 i번째 dp가 된다.
}
}
}
아까 위의 재귀처럼 탐색 방향만 바꾸면 되지 않을까?? 즉, 맨 뒤에서부터 오름차순으로 구하면 된다는 의미다! 즉, LDS는 다음과 같이 구성할 수 있다.
// 뒤에서부터 시작
for (int i = N - 1; i >= 0; i--) {
dp[i] = 1;
// 맨 뒤에서 i 이전 원소들을 탐색
for (int j = N - 1; j > i; j--) {
// i번째 원소가 j번째 원소보다 크면서 i번째 dp가 j번째 dp+1 값보다 작은경우
if (seq[j] < seq[i] && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1; // j번쨰 원소의 +1이 i번쨰 dp값이 됨
}
}
}
위 알고리즘은 11722번 가장 긴 감소하는 부분 수열 문제에서 그대로 적용하면 되므로 이 문제도 같이 풀면 좋을 것 같다.
- 4가지 방법을 사용하여 풀이한다.
위에서 설명한 두 가지 알고리즘 (Top-Down, Bottom-Up) 들과 입력방식에 따른 성능차를 같이 보도록 하자.
1 . Scanner + Top-Down
2. BufferedReader + Top-Down
3 . Scanner + Bottom-Up
4. BufferedReader + Bottom-Up
- 풀이
- 방법 1 : [Scanner + Top-Down]
import java.util.Scanner;
public class Main {
static Integer[] r_dp;
static Integer[] l_dp;
static int[] seq;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
r_dp = new Integer[N]; // LIS dp
l_dp = new Integer[N]; // LDS dp
seq = new int[N];
for (int i = 0; i < N; i++) {
seq[i] = in.nextInt();
}
for (int i = 0; i < N; i++) {
LIS(i);
LDS(i);
}
int max = -1;
for (int i = 0; i < N; i++) {
max = Math.max(r_dp[i] + l_dp[i], max);
}
System.out.println(max - 1);
}
static int LIS(int N) {
// 만약 탐색하지 않던 위치의 경우
if (r_dp[N] == null) {
r_dp[N] = 1; // 1로 초기화
// N 이전의 노드들을 탐색
for (int i = N - 1; i >= 0; i--) {
// 이전의 노드 중 seq[N]의 값보다 작은 걸 발견했을 경우
if (seq[i] < seq[N]) {
r_dp[N] = Math.max(r_dp[N], LIS(i) + 1);
}
}
}
return r_dp[N];
}
static int LDS(int N) {
// 만약 탐색하지 않던 위치의 경우
if (l_dp[N] == null) {
l_dp[N] = 1; // 1로 초기화
// N 이후의 노드들을 탐색
for (int i = N + 1; i < l_dp.length; i++) {
// 이후의 노드 중 seq[N]의 값보다 작은 걸 발견했을 경우
if (seq[i] < seq[N]) {
l_dp[N] = Math.max(l_dp[N], LDS(i) + 1);
}
}
}
return l_dp[N];
}
}
가장 기본적인 방법이라 할 수 있겠다.
주의할 점은 LIS, LDS를 구할 때 모든 값에 대하여 탐색해주어야 한다.
- 방법 2 : [BufferedReader + Top-Down]
입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 단, BufferedReader 는 문자열을 한 줄로 읽기 때문에 공백을 기준으로 문자열을 분리해주기 위해 StringTokenizer 을 사용하여 풀도록 하겠다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
static Integer[] r_dp;
static Integer[] l_dp;
static int[] seq;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
r_dp = new Integer[N]; // LIS dp
l_dp = new Integer[N]; // LDS dp
seq = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < N; i++) {
seq[i] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i < N; i++) {
LIS(i);
LDS(i);
}
int max = -1;
for (int i = 0; i < N; i++) {
max = Math.max(r_dp[i] + l_dp[i], max);
}
System.out.println(max - 1);
}
static int LIS(int N) {
// 만약 탐색하지 않던 위치의 경우
if (r_dp[N] == null) {
r_dp[N] = 1; // 1로 초기화
// N 이전의 노드들을 탐색
for (int i = N - 1; i >= 0; i--) {
// 이전의 노드 중 seq[N]의 값보다 작은 걸 발견했을 경우
if (seq[i] < seq[N]) {
r_dp[N] = Math.max(r_dp[N], LIS(i) + 1);
}
}
}
return r_dp[N];
}
static int LDS(int N) {
// 만약 탐색하지 않던 위치의 경우
if (l_dp[N] == null) {
l_dp[N] = 1; // 1로 초기화
// N 이후의 노드들을 탐색
for (int i = N + 1; i < l_dp.length; i++) {
// 이후의 노드 중 seq[N]의 값보다 작은 걸 발견했을 경우
if (seq[i] < seq[N]) {
l_dp[N] = Math.max(l_dp[N], LDS(i) + 1);
}
}
}
return l_dp[N];
}
}
크게 어려울 것은 없을 거라 생각한다. 거의 대부분 반복문으로 풀었다만 재귀로 푸는 것도 학습에 도움이 되니 한 번씩 차근차근 코드를 뜯어봤으면 한다.
- 방법 3 : [Scanner + Bottom-Up]
Top-Down 방식이 아닌 반복문으로 풀어내는 방식이다. 대부분 이분탐색 알고리즘 제외하고 이 방법을 가장 많이 사용한 것 같다. 반복문이 익숙해서 그런가...?
import java.util.Scanner;
public class Main {
static int N;
static int[] seq;
static int[] r_dp;
static int[] l_dp;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
N = in.nextInt();
r_dp = new int[N]; // LIS
l_dp = new int[N]; // LDS
seq = new int[N];
for (int i = 0; i < N; i++) {
seq[i] = in.nextInt();
}
LIS();
LDS();
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);
}
static void LIS() {
for(int i = 0; i < N; i++) {
r_dp[i] = 1;
// 0 ~ i 이전 원소들 탐색
for(int j = 0; j < i; j++) {
// j번째 원소가 i번째 원소보다 작으면서 i번째 dp가 j번째 dp+1 값보다 작은경우
if(seq[j] < seq[i] && r_dp[i] < r_dp[j] + 1) {
r_dp[i] = r_dp[j] + 1; // j번째 원소의 +1 값이 i번째 dp가 된다.
}
}
}
}
static void LDS() {
// 뒤에서부터 시작
for (int i = N - 1; i >= 0; i--) {
l_dp[i] = 1;
// 맨 뒤에서 i 이전 원소들을 탐색
for (int j = N - 1; j > i; j--) {
// i번째 원소가 j번째 원소보다 크면서 i번째 dp가 j번째 dp+1 값보다 작은경우
if (seq[j] < seq[i] && l_dp[i] < l_dp[j] + 1) {
l_dp[i] = l_dp[j] + 1; // j번쨰 원소의 +1이 i번쨰 dp값이 됨
}
}
}
}
}
탐색 방향만 바꾸어주면 되므로 크게 어렵지 않았을 것이다. 물론 순방향으로도 내림차순 부분수열을 구할 수 있다만, 그림으로 연상하기에는 이 방법이 더 편할 것 같아 탐색 방향을 바꾸는 걸로 택했다.
- 방법 4 : [BufferedReader + Bottom-Up]
마찬가지로 입력방식을 바꾼 것.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
static int N;
static int[] seq;
static int[] r_dp;
static int[] l_dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
r_dp = new int[N]; // LIS
l_dp = new int[N]; // LDS
seq = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < N; i++) {
seq[i] = Integer.parseInt(st.nextToken());
}
LIS();
LDS();
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);
}
static void LIS() {
for(int i = 0; i < N; i++) {
r_dp[i] = 1;
// 0 ~ i 이전 원소들 탐색
for(int j = 0; j < i; j++) {
// j번째 원소가 i번째 원소보다 작으면서 i번째 dp가 j번째 dp+1 값보다 작은경우
if(seq[j] < seq[i] && r_dp[i] < r_dp[j] + 1) {
r_dp[i] = r_dp[j] + 1; // j번째 원소의 +1 값이 i번째 dp가 된다.
}
}
}
}
static void LDS() {
// 뒤에서부터 시작
for (int i = N - 1; i >= 0; i--) {
l_dp[i] = 1;
// 맨 뒤에서 i 이전 원소들을 탐색
for (int j = N - 1; j > i; j--) {
// i번째 원소가 j번째 원소보다 크면서 i번째 dp가 j번째 dp+1 값보다 작은경우
if (seq[j] < seq[i] && l_dp[i] < l_dp[j] + 1) {
l_dp[i] = l_dp[j] + 1; // j번쨰 원소의 +1이 i번쨰 dp값이 됨
}
}
}
}
}
- 성능
채점 번호 : 22287974 - 방법 4 : BufferedReader + Bottom-Up
채점 번호 : 22287972 - 방법 3 : Scanner + Bottom-Up
채점 번호 : 22287968 - 방법 2 : BufferedReader + Top-Down
채점 번호 : 22287965 - 방법 1 : Scanner + Top-Down
- 정리
바이토닉의 개념에 대해 알아보고 양 방향으로 LIS, LDS를 구하면서 둘을 합한 것이 바이토닉 수열이 된다는 것을 볼 수 있었다. 오히려 이 문제를 풀기 전에 11722번 문제로 LDS를 접해보는 것도 좋을 것 같단 생각이 들지만,, 여간 혹여 모르거나 어려운 부분이 있다면 언제든 댓글 남겨주시라.
'JAVA - 백준 [BAEK JOON] > 동적 계획법 1' 카테고리의 다른 글
| [백준] 9251번 : LCS - JAVA [자바] (31) | 2020.09.08 |
|---|---|
| [백준] 2565번 : 전깃줄 - JAVA [자바] (11) | 2020.09.04 |
| [백준] 11053번 : 가장 긴 증가하는 부분 수열 - JAVA [자바] (16) | 2020.09.02 |
| [백준] 2156번 : 포도주 시식 - JAVA [자바] (20) | 2020.08.31 |
| [백준] 10844번 : 쉬운 계단 수 - JAVA [자바] (46) | 2020.08.29 |