C++에서 가장 길게 증가하는 부분 수열(LIS)의 개수 구하기

문제 개요

정렬되지 않은 정수 배열이 하나 주어졌을 때, 가장 길게 증가하는 부분 수열(Longest Increasing Subsequence, LIS)의 개수를 구하는 것이 목표입니다. 예를 들어 입력이 [1, 3, 5, 4, 7]이라면, 길이가 4인 증가 부분 수열은 [1, 3, 5, 7]과 [1, 3, 4, 7] 두 가지가 존재하므로 정답은 2가 됩니다.

접근 방법: 동적 계획법

이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 인덱스마다 다음 두 가지 정보를 함께 추적하는 것입니다.

• len[i]: 인덱스 i를 끝점으로 하는 가장 긴 증가 부분 수열의 길이
• cnt[i]: 인덱스 i를 끝점으로 하면서 길이가 len[i]인 증가 부분 수열의 개수

알고리즘의 전체 흐름은 다음과 같습니다 −

• n := nums 배열의 크기로 설정하고, 크기가 n인 두 배열 len과 cnt를 생성한 뒤 모든 값을 1로 초기화합니다.
• lis := 1로 초기화합니다.
• i를 1부터 n−1까지 순회합니다.
  • j를 0부터 i−1까지 순회합니다.
    • nums[i] > nums[j]인 경우,
      • 만약 len[j] + 1 > len[i]라면, len[i] := len[j] + 1로 갱신하고 cnt[i] := cnt[j]로 설정합니다.
      • 그렇지 않고 len[j] + 1 == len[i]라면, cnt[i] := cnt[i] + cnt[j]로 경로의 수를 누적합니다.
  • lis := max(lis, len[i])로 갱신합니다.
• ans := 0으로 초기화합니다.
• i를 0부터 n−1까지 순회하면서, len[i] == lis인 경우 ans := ans + cnt[i]를 수행합니다.
• 최종적으로 ans를 반환합니다.

C++ 구현 예시

아래 구현 코드를 통해 더 자세히 이해해 보겠습니다 −

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int findNumberOfLIS(vector<int>& nums) {
      int n = nums.size();
      vector <int> len(n, 1), cnt(n, 1);
      int lis = 1;
      for(int i = 1; i < n; i++){
         for(int j = 0; j < i; j++){
            if(nums[i] > nums[j]){
               if(len[j] + 1 > len[i]){
                  len[i] = len[j] + 1;
                  cnt[i] = cnt[j];
               }
               else if(len[j] + 1 == len[i]){
                  cnt[i] += cnt[j];
               }
            }
            lis = max(lis, len[i]);
         }
      }
      int ans = 0;
      for(int i = 0; i < n; i++){
         if(len[i] == lis)ans += cnt[i];
      }
      return ans;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,3,5,4,7};
   cout << (ob.findNumberOfLIS(v));
}

입력

[1,3,5,4,7]

출력

2

복잡도 분석

시간 복잡도: O(n²) — 모든 인덱스 쌍 (i, j)을 비교하는 두 개의 중첩 루프가 사용되기 때문입니다.
공간 복잡도: O(n) — 각 인덱스의 수열 길이와 개수를 저장하기 위한 두 개의 1차원 배열이 필요하기 때문입니다.