C++에서 가장 긴 증가 하위 시퀀스 알고리즘을 사용하는 방법

C++에서 최장 증가 부분 수열 알고리즘을 사용하려면 특정 코드 예제가 필요합니다.

최장 증가 부분 수열(LIS)은 고전적인 알고리즘 문제이며 해당 솔루션 아이디어는 데이터 처리, 그래프 이론과 같은 여러 분야에 적용될 수 있습니다. , 등. 이번 글에서는 C++에서 가장 길게 증가하는 하위 시퀀스 알고리즘을 사용하는 방법을 소개하고 구체적인 코드 예제를 제공하겠습니다.

먼저, 가장 긴 증가 부분 수열의 정의를 이해해 봅시다. a1, a2, ..., an 시퀀스가 주어지면 원래 시퀀스에서 b 요소의 상대적 순서가 증가하는 가장 긴 하위 시퀀스 b1, b2, ..., bm을 찾아야 합니다. 즉, 임의의 i ai가 만족되면 bj > bi도 존재합니다. 가장 긴 증가 부분 수열의 길이는 m입니다.

다음으로 가장 긴 증가 부분 수열을 해결하기 위한 두 가지 일반적인 알고리즘인 동적 프로그래밍 알고리즘과 그리디 알고리즘을 소개하겠습니다.

1. 동적 계획법 알고리즘

동적 계획법 알고리즘은 가장 긴 부분 수열의 풀이 과정을 여러 단계로 나누고 그 결과를 2차원 배열 dp에 저장합니다. dp[i]는 시퀀스의 i번째 요소로 끝나는 가장 긴 증가 부분 시퀀스의 길이를 나타냅니다.

구체적인 해결 과정은 다음과 같습니다.

• dp 배열의 모든 요소를 1로 초기화합니다. 이는 각 요소로 끝나는 하위 시퀀스의 길이가 최소 1이라는 의미입니다.
• 전체 시퀀스를 왼쪽에서 오른쪽으로 탐색하고 각 위치 i에 대해 dp[i] 값을 계산합니다.
• 각 위치 i에 대해 이전 위치 j를 탐색합니다. aj

최종 결과는 dp 배열의 최대값입니다.

다음은 C++에서 동적 프로그래밍 알고리즘을 구현하기 위한 코드 예제입니다.

#include #include using namespace std; int longestIncreasingSubsequence(vector& nums) { int n = nums.size(); vector dp(n, 1); for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (nums[j] < nums[i]) { dp[i] = max(dp[i], dp[j]+1); } } } int res = 0; for (int i = 0; i < n; i++) { res = max(res, dp[i]); } return res; } int main() { vector nums = {10, 9, 2, 5, 3, 7, 101, 18}; int res = longestIncreasingSubsequence(nums); cout << "最长递增子序列的长度为：" << res << endl; return 0; }

2. 그리디 알고리즘

그리디 알고리즘은 최장 증가 하위 시퀀스 문제를 해결하는 더 효율적인 방법입니다. 이 알고리즘은 보조 배열 d를 사용하여 현재 가장 긴 증가 부분 수열의 마지막 요소를 저장합니다. 전체 시퀀스를 탐색하고 각 요소에 대해 이진 검색을 사용하여 보조 배열 d에서의 위치를 결정합니다.

구체적인 해결 과정은 다음과 같습니다.

• 보조 배열 d를 빈 배열로 초기화합니다.
• 전체 시퀀스를 왼쪽에서 오른쪽으로 순회합니다. 각 요소 a에 대해 a가 d의 끝 요소보다 크면 d의 끝에 a를 추가합니다.
• a가 d의 마지막 요소보다 작거나 같은 경우 이진 검색을 사용하여 d에서 a보다 크거나 같은 첫 번째 요소를 찾아 a로 바꿉니다.

최종 결과는 보조 배열의 길이 d입니다.

다음은 그리디 알고리즘을 C++로 구현한 코드 예제입니다.

#include #include using namespace std; int longestIncreasingSubsequence(vector& nums) { vector d; for (auto num : nums) { int left = 0, right = d.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; if (d[mid] < num) { left = mid + 1; } else { right = mid - 1; } } if (left >= d.size()) { d.push_back(num); } else { d[left] = num; } } return d.size(); } int main() { vector nums = {10, 9, 2, 5, 3, 7, 101, 18}; int res = longestIncreasingSubsequence(nums); cout << "最长递增子序列的长度为：" << res << endl; return 0; }

위는 C++에서 최장 증가 하위 시퀀스 알고리즘을 사용하는 방법에 대한 소개 및 코드 예제입니다. 동적 프로그래밍 알고리즘이든 그리디 알고리즘이든 O(n^2) 또는 O(nlogn)의 시간 복잡도를 사용하여 가장 길게 증가하는 부분 수열 문제를 해결할 수 있습니다. 독자는 특정 애플리케이션 시나리오에 따라 사용할 적절한 알고리즘을 선택할 수 있습니다. 이 글이 모든 사람이 최장 증가 부분 수열 알고리즘을 이해하는 데 도움이 되기를 바랍니다.

위 내용은 C++에서 가장 긴 증가 하위 시퀀스 알고리즘을 사용하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!