Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++ 백트래킹으로 증가하는 부분 수열 모두 찾기

문제 소개

정수 배열이 주어졌을 때, 해당 배열에서 만들 수 있는 모든 증가 부분 수열(increasing subsequence)을 찾아야 합니다. 이때 각 부분 수열의 길이는 최소 2 이상이어야 한다는 조건이 있습니다.

예를 들어 배열이 [4, 6, 7, 7]이라면 출력은 다음과 같습니다.

[[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7, 7], [4, 7, 7]]

주의할 점은, 값이 같은 원소가 여러 개 있더라도 동일한 부분 수열이 중복해서 출력되지 않도록 처리해야 한다는 것입니다.

알고리즘 접근 방법

이 문제는 백트래킹(backtracking) 기법으로 깔끔하게 해결할 수 있습니다. 전체 흐름은 다음과 같습니다.

  1. 모든 결과를 저장할 배열 res를 준비합니다.
  2. nums 배열, 탐색 시작 위치 start, 현재까지 구성한 임시 수열 temp를 인자로 받는 solve() 함수를 정의합니다.
  3. temp의 크기가 1보다 크면(즉, 길이가 2 이상이면) res에 추가합니다.
  4. 같은 재귀 단계에서 중복된 값을 다시 선택하지 않도록 집합 visited를 생성합니다.
  5. start부터 배열 끝까지 반복하면서 다음을 수행합니다.
    • 현재 값을 x = nums[i]로 가져옵니다.
    • x가 이미 visited에 존재하면 이번 반복은 건너뜁니다.
    • 그렇지 않으면 x를 visited에 삽입합니다.
    • temp가 비어 있거나 temp의 마지막 원소가 x 이하라면, x를 temp에 추가하고 solve(nums, i + 1, temp)를 재귀 호출한 뒤, 백트래킹을 위해 마지막 원소를 제거합니다.
  6. 메인 함수에서 solve(nums, 0, temp)를 호출한 후 res를 반환합니다.

여기서 핵심 역할을 하는 것이 바로 visited 집합입니다. 각 재귀 호출 레벨에서 이미 시도한 값은 다시 선택하지 않음으로써, 입력 배열에 중복된 숫자가 포함되어 있어도 결과 부분 수열의 중복을 효과적으로 방지할 수 있습니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto>> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << "[";
      for(int j = 0; j <v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector<vector<int>> res;
   void solve(vector<int>& nums, int start, vector<int> temp){
      if(temp.size() > 1){
         res.push_back(temp);
      }
      set<int> visited;
      for(int i = start; i < nums.size(); i++){
         int x = nums[i];
         if(visited.count(x)) continue;
         visited.insert(x);
         if(temp.empty() || temp[temp.size() - 1] <= x){
            temp.push_back(x);
            solve(nums, i + 1, temp);
            temp.pop_back();
         }
      }
   }
   vector<vector<int>> findSubsequences(vector<int>& nums) {
      res.clear();
      vector<int> temp;
      solve(nums, 0, temp);
      return res;
   }
};
main(){
   vector<int> v = {5, 6, 7, 8};
   Solution ob;
   print_vector(ob.findSubsequences(v));
}

입력

[5, 6, 7, 8]

출력

[[5, 6], [5, 6, 7], [5, 6, 7, 8], [5, 6, 8], [5, 7], [5, 7, 8], [5, 8], [6, 7], [6, 7, 8], [6, 8], [7, 8]]

복잡도 분석

  • 시간 복잡도: 최악의 경우 O(2N)입니다. 각 원소마다 부분 수열에 포함하거나 제외하는 두 가지 선택지가 존재하기 때문입니다. 다만 visited 집합 덕분에 중복되는 탐색 경로는 가지치기됩니다.
  • 공간 복잡도: 재귀 호출 깊이와 임시 수열 저장에 O(N)이 필요하며, 결과를 저장하는 데는 생성되는 부분 수열의 개수만큼 추가 공간이 필요합니다.