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<iostream>
#include<vector>
using namespace std;

int longestIncreasingSubsequence(vector<int>& nums) {
  int n = nums.size();
  vector<int> 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<int> 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<iostream>
#include<vector>
using namespace std;

int longestIncreasingSubsequence(vector<int>& nums) {
  vector<int> 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<int> 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!