백준 11054: 가장 긴 바이토닉 부분 수열
/ 9분 분량 / 문제 풀이
Gold_IV 난이도 문제를 C++로 풀이한 내용입니다. 수열을 증가하다가 감소하는 형태의 가장 긴 부분 수열의 길이를 찾는 문제입니다.
백준 11054: 가장 긴 바이토닉 부분 수열
Gold_IV 난이도 문제를 C++로 풀이한 내용입니다. 수열을 증가하다가 감소하는 형태의 가장 긴 부분 수열의 길이를 찾는 문제입니다.
문제 소개
- 문제 번호: 11054
- 문제 제목: 가장 긴 바이토닉 부분 수열
- 난이도: Gold_IV
- 사용 언어: C++
- 실행 시간: 0 ms
- 메모리: 2152 KB
- 문제 요약: 주어진 수열에서 증가하는 부분 수열과 감소하는 부분 수열이 이어지는 가장 긴 바이토닉 부분 수열의 길이를 구하는 문제입니다. 증가하는 부분과 감소하는 부분은 하나의 숫자를 공유할 수 있습니다.
접근 방법
- 문제 이해: 바이토닉 부분 수열은 어떤 지점을 기준으로 증가하다가 감소하는 형태입니다. 예를 들어, 1, 3, 5, 4, 2 와 같은 형태입니다. 문제는 이러한 바이토닉 부분 수열 중 가장 긴 것의 길이를 찾는 것입니다.
- 알고리즘/자료구조:
- LIS (Longest Increasing Subsequence): 가장 긴 증가하는 부분 수열 알고리즘을 사용합니다.
- LDS (Longest Decreasing Subsequence): 가장 긴 감소하는 부분 수열 알고리즘을 사용합니다. (이 문제에서는 역으로 증가하는 부분 수열로 계산)
- Vector: 수열의 값을 저장하고, LIS와 LDS 값을 저장하기 위해 사용합니다.
- 방법 선택 이유: 바이토닉 부분 수열은 증가하는 부분과 감소하는 부분으로 나눌 수 있습니다. 각 숫자를 기준으로, 해당 숫자를 포함하는 가장 긴 증가하는 부분 수열의 길이와, 해당 숫자를 포함하는 가장 긴 감소하는 부분 수열의 길이를 구하면, 이 두 길이를 합하고 중복되는 숫자를 1개로 세기 위해 1을 빼주면 해당 숫자를 꼭지점으로 하는 바이토닉 부분 수열의 길이를 구할 수 있습니다. 모든 숫자를 기준으로 이 과정을 반복하여 최댓값을 찾으면 됩니다. LIS는 앞에서부터, LDS는 뒤에서부터 계산하는 것이 효율적입니다. LDS는 실제로는 수열을 뒤집거나, 뒤에서부터 앞으로 가는 LIS를 계산하는 것과 같습니다.
풀이 과정
- 입력 받기: 주어진 수열의 크기 N과 수열의 원소들을 입력받아
A벡터에 저장합니다. (1-based indexing을 위해 크기를 N+1로 합니다.) - LIS 계산:
LIS벡터를 초기화합니다. 각i에 대해LIS[i]는A[i]를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이를 저장합니다.A[i]자신만으로 길이 1인 부분 수열을 만들 수 있으므로LIS[i]를 1로 초기화합니다. 이후j가 1부터i-1까지 반복하면서A[j] < A[i]인 경우,LIS[i]를LIS[j] + 1과 현재LIS[i]값 중 더 큰 값으로 갱신합니다. - LDS 계산:
LDS벡터를 초기화합니다.LDS[i]는A[i]를 시작으로 하는 가장 긴 감소하는 부분 수열의 길이를 저장합니다. 이는 수열을 역으로 생각하여A[i]를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이와 같습니다. 따라서i를N부터 1까지 역순으로 반복합니다.A[i]자신만으로 길이 1인 부분 수열을 만들 수 있으므로LDS[i]를 1로 초기화합니다. 이후j가N부터i+1까지 반복하면서A[j] < A[i]인 경우,LDS[i]를LDS[j] + 1과 현재LDS[i]값 중 더 큰 값으로 갱신합니다. - 최대 바이토닉 길이 계산:
answer변수를 0으로 초기화합니다.i를 1부터N까지 반복하면서LIS[i] + LDS[i] - 1값을answer와 비교하여 최댓값을answer에 저장합니다. 여기서 1을 빼는 이유는A[i]가 LIS와 LDS에서 중복으로 계산되기 때문입니다. - 결과 출력: 최종적으로 계산된
answer값을 출력합니다.
코드 설명
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); // 표준 입출력 버퍼와 C 스타일 입출력 동기화를 비활성화하여 입출력 속도를 향상시킵니다.
cin.tie(nullptr); // cin과 cout의 tie를 해제하여 입력이 끝나기 전에 출력을 할 수 있도록 합니다.
int N; // 수열의 크기
cin >> N; // 수열의 크기를 입력받습니다.
vector<int> A(N + 1); // 수열을 저장할 벡터 (1-based indexing을 위해 크기를 N+1로 설정)
vector<int> LIS(N + 1); // 각 인덱스 i에 대해, A[i]를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이를 저장
vector<int> LDS(N + 1); // 각 인덱스 i에 대해, A[i]를 시작으로 하는 가장 긴 감소하는 부분 수열의 길이를 저장 (실제로는 뒤에서부터 계산하는 LIS)
for (int i = 1; i <= N; i++) {
cin >> A[i]; // 수열의 원소들을 입력받습니다.
}
// LIS (Longest Increasing Subsequence) 계산
for (int i = 1; i <= N; i++) {
LIS[i] = 1; // 자기 자신만 선택하는 경우, 길이는 1입니다.
for (int j = 1; j < i; j++) {
// A[j]가 A[i]보다 작으면, A[i]를 A[j]로 끝나는 LIS에 이어 붙일 수 있습니다.
if (A[j] < A[i]) {
LIS[i] = max(LIS[i], LIS[j] + 1); // 기존 LIS[i] 값과 LIS[j] + 1 중 더 큰 값으로 갱신합니다.
}
}
}
// LDS (Longest Decreasing Subsequence) 계산 (역으로 LIS 계산)
for (int i = N; i >= 1; i--) {
LDS[i] = 1; // 자기 자신만 선택하는 경우, 길이는 1입니다.
for (int j = N; j > i; j--) {
// A[j]가 A[i]보다 작으면, A[i]를 A[j]로 시작하는 LDS에 이어 붙일 수 있습니다. (여기서는 A[i]가 더 크므로, A[i]가 이전 요소가 됨)
// A[j] < A[i] 조건은 A[i]를 앞에 두고 A[j]를 뒤에 두는 감소 수열을 만들기 위함입니다.
if (A[j] < A[i]) {
LDS[i] = max(LDS[i], LDS[j] + 1); // 기존 LDS[i] 값과 LDS[j] + 1 중 더 큰 값으로 갱신합니다.
}
}
}
int answer = 0; // 최종적인 가장 긴 바이토닉 부분 수열의 길이를 저장할 변수
for (int i = 1; i <= N; i++) {
// 각 원소 A[i]를 꼭지점으로 하는 바이토닉 부분 수열의 길이는 LIS[i] + LDS[i] - 1 입니다.
// A[i]가 LIS와 LDS에서 중복으로 계산되므로 1을 빼줍니다.
answer = max(answer, LIS[i] + LDS[i] - 1);
}
cout << answer; // 계산된 최대 길이를 출력합니다.
return 0; // 프로그램 정상 종료
}
복잡도 분석
- 시간 복잡도:
- LIS 계산: 이중 반복문으로 O(N^2)
- LDS 계산: 이중 반복문으로 O(N^2)
- 최대 길이 계산: 단일 반복문으로 O(N)
- 총 시간 복잡도: O(N^2)
- 공간 복잡도:
A벡터: O(N)LIS벡터: O(N)LDS벡터: O(N)- 총 공간 복잡도: O(N)
배운 점
- 바이토닉 부분 수열이라는 개념을 LIS와 LDS를 조합하여 해결할 수 있다는 것을 배웠습니다.
- 특정 원소를 기준으로 LIS와 LDS를 계산하여 합치는 아이디어가 문제 해결의 핵심임을 알게 되었습니다.
- LDS를 계산할 때, 수열을 역순으로 보거나 뒤집어서 LIS를 계산하는 것과 같은 원리임을 이해했습니다.
- 1-based indexing을 사용하면 코드 가독성과 구현이 편리할 수 있음을 다시 한번 확인했습니다.