https://www.acmicpc.net/problem/11053
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <utility>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
vector<int> arr;
for(int i = 0; i < N; i++){
int x;
cin >> x;
arr.push_back(x);
}
sort(arr.begin(), arr.end());
arr.erase(unique(arr.begin(), arr.end()), arr.end());
cout << arr.size();
return 0;
}
입력 받은 배열을 오름차순으로 정렬하고 중복되는 원소들을 삭제하면, 가장 긴 증가하는 부분 수열이 나오는 줄 알았다. 그런데 오답이다!
그 이유는 부분 수열은 기존 수열로부터 구할 수 있어야 하는데, 정렬을 통해 원소들의 순서를 마음대로 바꿔버리면 기존 수열로부터 절대 나올 수 없는 부분 수열이 정답으로 출력될 수도 있기 때문이다.
참고: https://tjdahr25.tistory.com/18
문제의 예시로 나온 A = {10, 20, 10, 30, 20, 50} 수열을 통해 점화식을 도출해보자.
dp[i]에는 i번째 항 앞쪽 (0 ~ i-1)에 있는 i번째 항보다 작은 수들 중에서, dp 테이블의 최댓값에 1을 더한 값
을 저장하면 된다. 만약 자신의 앞쪽에 자신보다 작은 수가 없다면, 자기 자신만 가장 긴 증가하는 부분 수열이므로 길이는 1이다.
이렇게 dp 테이블에 값을 저장하고, 그 중에서 최댓값이 가장 긴 증가하는 부분 수열의 길이가 된다.
arr[0]의 앞쪽에 다른 수가 없으므로 dp[0] = 1
arr[1]의 앞쪽에 20보다 작은 수 10이 있으므로, 그 dp 테이블의 값에 1을 더하면 dp[1] = 2
arr[2]의 앞쪽에 10보다 작은 수가 없으므로, dp[2] = 1
arr[3]의 앞쪽에 30보다 작은 수는 10과 20이고 dp[1] = 2가 최대이므로 거기에 1을 더하면, dp[3] = 3
arr[4]의 앞쪽에 20보다 작은 수는 10이므로, dp[4] = 2
arr[5]의 앞쪽에 50보다 작은 수는 10, 20, 30인데 그 중에서 dp[3] = 3이 최대이므로 거기에 1을 더하면, dp[4] = 4
dp 테이블에서 최댓값인 4가 가장 긴 증가하는 부분 수열의 길이가 된다.
#include <iostream>
#include <vector>
using namespace std;
const int MAX = 1001;
int arr[MAX];
int dp[MAX];
int maxLength = 0;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
for(int i = 0; i < N; i++){
cin >> arr[i];
}
for (int i = 0; i < N; i++) {
int tmp = 0;
// i보다 앞쪽에 있으면서
for (int j = 0; j < i; j++) {
// i번째 값보다 작은 원소들 중에
if (arr[j] < arr[i]) {
// dp 테이블의 최댓값 구하기
tmp = max(tmp, dp[j]);
}
}
dp[i] = tmp + 1; // 거기에 1을 더해서 dp 테이블 갱신
maxLength = max(dp[i], maxLength); // dp 테이블의 최댓값 갱신
}
cout << maxLength;
return 0;
}
위 코드의 시간 복잡도는 이중 for문을 돌기 때문에 O(N^2)이라고 할 수 있다.
이중 for문을 도는 이유는, 외부 루프에서 arr 배열을 순회하며, 내부 루프에서는 자신보다 작은 수들 중에 dp 테이블의 값은 최대인 위치
을 찾기 위해 arr배열을 다시 순회하기 때문이다.
그런데, 여기서 그 최적의 위치를 찾는 것을 O(logN)으로 줄여서 시간 복잡도를 O(N*logN)으로 줄일 수 있다. 그 방법은 다음 포스트에서 알아보겠다!