https://cppking.tistory.com/220
기존에 LIS 문제에 대해 작성한 글인데 여기서는 특정 숫자부터 시작해서 끝까지 증가하는 수열을 셌을 때 길이를 cache에 저장했었다. 이 방법은 재귀를 사용하는데 계산이 많아지면 시간 초과 오류가 발생하므로 다른 방법도 알고 있어야 한다.
https://cocoon1787.tistory.com/455
[C/C++] 백준 14002번 - 가장 긴 증가하는 부분 수열 4 (LIS)
#include #include #include using namespace std; int N, A[1001], len; int index, tmp; int dp[1001]; vector v; int main() { cin >> N; for (int i = 1; i > A[i]; len = 0; for (int j = 1; j < i; j++) { if (A[j] < A[i]) len = max(dp[j], len); } dp[i] = len + 1;
cocoon1787.tistory.com
이 방법은 바텀업 방식으로 처음 숫자부터 특정 숫자까지 증가하는 수열의 길이를 cache에 저장한다. 재귀를 사용하지 않고 길이 뿐만 아니라 LIS의 요소들도 구할 수 있다. 그리고 이중 루프라서 N^2 속도를 가지는데 algorithm 의 lower_bound를 이용하면 속도를 NlogN으로 줄일 수 있다. lower_bound로 가장 처음으로 만나는 자신과 같거나 큰 수의 index를 구할 수 있는데 그것을 이용해서 ㅇLIS를 구할 수 있다.
'백준' 카테고리의 다른 글
| [백준] 17266번 - 이분 탐색 (1) | 2024.03.18 |
|---|---|
| [백준] 11723번 - 비트마스킹 (0) | 2024.03.18 |
| [백준] 2294번 - 동전 2 (동적 계획법) (0) | 2023.03.10 |
| [백준] 2293번 - 동전 1 (동적 계획법) (0) | 2023.03.06 |
| [백준] 9251번 - 동적계획법 LCS (0) | 2023.03.03 |