[C++] 백준(BOJ) - 11053 : 가장 긴 증가하는 부분 수열 (LIS)
인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.
문제
BOJ - 11053 : 가장 긴 증가하는 부분 수열 (LIS)(링크)
수열 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 ≤ $A_i$ ≤ 1,000)
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
알고리즘
- LIS (Longest Increase Sequence)
풀이
- 숫자의 시각화
- 이중 for문을 활용하는 방법
- i를 옮겨가며 이전 인덱스들을 확인한다
- maxValue를 갱신해나가며 cnt[] 배열에 삽입
- lower_bound를 사용
- lower_bound
- 0번째 배열의 원소부터 찾아서 어떠한 값의 “이상이 되는 위치”를 반환
- lowerPos에 “현재의 증가 수열 길이” 중에서 num보다 작거나 같은 값의 위치를 찾는다
- 만약 len 안에 없다면 *lowerPos는 0을 반환. 왜냐면 초기화를 0으로 하기 때문. *lowerPos에 해당 값을 넣어서 배열을 변화시키고 len을 증가시킨다
- 만약 len 안에 있다면 *lowerPos는 작거나 같은 위치를 반환하고 그 값은 이제 좀 더 작거나 같은 값으로 변화
- lower_bound
- 이터레이터는 포인터가 아니다
- *가 오버로딩되있어 “포인터” 처럼 쓸 수 있다
- 스마트 포인터 : 컨테이너 안을 순회하며 컨테이너 안의 특정 위치를 가리킨다
- vector, deque, string은 포인터끼리 더하고 빼고 비교할 수 있으며, random access iterator 라고도 불린다
*lower_bound는 정렬된 상태에서만 사용하여야 함*
코드 1 : 이중 for문
// BOJ - 11053 : 가장 긴 증가하는 부분 수열
#include <bits/stdc++.h>
using namespace std;
int n, a[1004], cnt[1004], res;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++)
{
int maxValue = 0;
for (int j = 0; j < i; j++)
{
if (a[j] < a[i] && maxValue < cnt[j]) maxValue = cnt[j];
}
cnt[i] = maxValue + 1;
res = max(res, cnt[i]);
}
cout << res;
return 0;
}
코드 2 : lower_bound
// BOJ - 11053 : 가장 긴 증가하는 부분 수열
#include <bits/stdc++.h>
using namespace std;
long long n, lis[10000004], len, num;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> num;
auto lowerPos = lower_bound(lis, lis + len, num);
if (*lowerPos == 0) len++;
*lowerPos = num;
}
cout << len;
return 0;
}
평가
- LIS는 자주 나오는 유형은 아니지만 풀이방법을 모르면 굉장히 코드가 어렵기 때문에 통으로 암기
- O($N^2$)의 시간복잡도를 갖는 풀이 방법
