문제
가장 긴 증가하는 부분 수열 2
풀이
알고리즘
- 증가하는 부분 수열을 넣어줄 빈 배열을 선언하고 초기값으로 문제에서 제시하는 A_i의 범위보다 작은 값을 하나 넣어준다.
vector<int> vec(1, 0);
- input으로 주어지는 N만큼 반복하면서
for (int i = 0; i < N; i++)2-1. 만약 A[i]가 vec의 마지막 값보다 '크다면' vec에 A[i]를 추가(push_back)해준다.
if (temp > vec.back()) vec.push_back(temp);2-2. 그 외의 경우 lower_bound 함수를 통해 vec에서 A[i]와 같은 값을 찾은 후(A[i]가 존재하지 않는다면 바로 다음으로 큰 값) 해당 위치의 값을 A[i]로 바꿔준다.
else { auto low = lower_bound(vec.begin(), vec.end(), A[i]); *low = A[i]; }
- 본 알고리즘을 통해서 해당 문제를 풀어낼 수는 있지만, 문제점이 있다. 이는 아래에 테스트 케이스와 설명하도록 함.
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N;
void Solve(vector<int> A)
{
vector<int> vec(1, 0);
for (int i = 0; i < N; i++)
{
if (A[i] > vec.back())
vec.push_back(A[i]);
else
{
auto low = lower_bound(vec.begin(), vec.end(), A[i]);
*low = A[i];
}
}
cout << vec.size() - 1 << endl;
}
int main()
{
cin >> N;
vector<int> A(N);
for (int i = 0; i < N; i++)
cin >> A[i];
Solve(A);
}주석코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void Solve(int N, vector<int> A)
{
vector<int> vec(1, 0);
for (int i = 0; i < N; i++)
{
cout << "A[" << i << "] = " << A[i] << endl;
for (int i : vec)
cout << i << ' ';
cout << endl;
//넣고자하는 값이 vec의 마지막 값보다 크다면 넣어준다.
if (A[i] > vec.back())
vec.push_back(A[i]);
//넣고자하는 값이 vec의 마지막 값보다 작거나 같다면
else
{
//A[i]를 기존 vec안에서 찾아본다.
//A[i]가 있다면 그 iter를 돌려줄 것이고, 없다면 A[i]보다 큰 원소중 가장 처음 오는 iter를 반환해준다.
auto low = lower_bound(vec.begin(), vec.end(), A[i]);
//해당 iter에 해당되는 vec 값을 변경해준다.
*low = A[i];
}
for (int i : vec)
cout << i << ' ';
cout << "\n\n";
}
//초기값으로 넣어준 0을 제외한 vec의 길이가 가장 긴 증가하는 부분 수열의 길이가 된다.
cout << vec.size() - 1 << endl;
}
int main()
{
int N1 = 6;
vector<int> A1 = {10, 20, 10, 30, 20, 50};
int N2 = 8;
vector<int> A2 = {1, 3, 5, 7, 2, 6, 4, 7};
Solve(N2, A2);
}테스트 케이스 출력
A[0] = 1
0
0 1
A[1] = 3
0 1
0 1 3
A[2] = 5
0 1 3
0 1 3 5
A[3] = 7
0 1 3 5
0 1 3 5 7
A[4] = 2
0 1 3 5 7
0 1 2 5 7
A[5] = 6
0 1 2 5 7
0 1 2 5 6
A[6] = 4
0 1 2 5 6
0 1 2 4 6
A[7] = 7
0 1 2 4 6
0 1 2 4 6 7
5문제점
결론부터 말하자면 해당 알고리즘을 통해 '가장 긴 증가하는 부분 수열의 길이'는 구할 수 있지만, '가장 긴 증가하는 부분 수열'을 구할 수는 없다.
무슨 말인가 하면 사실 위 테스트 케이스의 가장 긴 증가하는 부분 수열은 [1, 3, 5, 6, 7]이다.
하지만 위의 테스트 케이스 출력을 보게 되면 마지막에 [1, 2, 4, 6, 7](초기값 0은 제외) 를 출력하고 마치는 것을 볼 수 있다.
이 문제는 아래 코드 부분에서 일어나는 문제로 볼 수 있다.auto low = lower_bound(vec.begin(), vec.end(), A[i]); *low = A[i];EX) 위 테스트 케이스 출력 A[4]=2 부분을 보자.
if문을 통해 해당 코드에서 현재 들어온 A[4]는 vec.back()보다 작거나 같은 값이다.
위 A[4]=2 이므로 lower_bound함수의 특성상 2를 찾지 못했으므로 그보다 큰 값중 가장 먼저 온 값의 인덱스인 2를 반환해준다(엄밀히 따지자면 iterator지만).
그 후에*low=A[4];를 통해 해당 인덱스 값을 A[4]로 바꿔준다.
이로 인해 본래 올바른 값이 될 터인 3을 2로 바꿔주는 상황이 벌어진다.
하지만 잘 생각해보자. 이 과정을 통해서 중간 값 3이 2로 바뀐다고 하여서 '가장 긴 부분수열의 길이'를 구하는데 문제가 생길까?
아무런 문제가 생기지 않는다.
이 과정은 vec '마지막 원소'가 새로 들어올 A[i]보다 크다면 바꿔주는 것에 그 의미가 있다.
그러므로 중간 값이 바뀌는 어찌보면 사소한 문제는 제쳐두고 전체적인 길이만을 생각하는 것이다.
참고한 글
