개념 요약
- 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 배열의 길이가 최대인 부분 수열이다.
- 간편한 풀이법은 DP를 이용하는 것이다.(시간 복잡도 : $O(n^2)$)
- 이분 탐색을 이용한 방법도 가능하다.(시간 복잡도 : $O(nlogn)$)
코드
// DP
void LIS_DP(vector<int> &arr)
{
// dp[i] : dp의 i번째 인덱스에서 끝나는 최장 증가 부분 수열의 길이
for (int i = 1; i < dp.size(); ++i)
{
// 해당 원소 초기화
dp[i] = 1;
// 처음부터 끝까지 루프
for (int i j = 0; j < dp.size(); ++j)
// 큰 값을 dp[i]에 넣는다.
dp[i] = max(dp[i], dp[j] + 1);
}
}
// 이분 탐색
int binary_search(vector<int> lis, int start, int end, int element)
{
while (start < end)
{
int mid = (start + end) / 2;
if (element > lis[mid])
start = mid + 1;
else
end = mid;
}
return (end);
}
int LIS_BS(vector<int> &arr)
{
int ret = 0;
vector<int> list;
list.push_back(arr[0]);
for (int i = 1; i < n; ++i)
{
if (arr[i] > lis.back())
{
lis.push_back(arr[i]);
ret = lis.size() - 1;
}
int pos = binary_search(lis, 0, ret, arr[i]);
lis[pos] = arr[i];
}
return (ret + 1);
}
'CS공부 > Algorithm' 카테고리의 다른 글
동적 계획법(Dynamic Programming) (0) | 2022.06.30 |
---|---|
최소 공통 조상(Lowest Common Ancestor) (0) | 2022.06.30 |
DFS & BFS (0) | 2022.06.29 |
해시 테이블(Hash Table) (0) | 2022.06.23 |
이분 탐색(Binary Search) (0) | 2022.06.22 |