C++로 증가하는 모든 부분 수열 개수 세기

이 튜토리얼에서는 배열에서 만들 수 있는 증가하는 부분 수열(increasing subsequence)의 개수를 구하는 방법을 다룹니다.

문제의 조건은 다음과 같습니다. 0부터 9까지의 숫자로 이루어진 배열이 주어지며, 우리는 배열 내에서 다음 원소가 항상 이전 원소보다 큰 모든 부분 수열의 개수를 세어야 합니다.

접근 방식

이 문제는 동적 계획법(DP)을 활용해 효율적으로 해결할 수 있습니다. 각 숫자(0~9)별로 해당 숫자로 끝나는 증가 부분 수열의 개수를 저장하는 카운트 배열을 사용합니다.

배열을 왼쪽에서 오른쪽으로 순회하면서, 현재 원소 arr[i]에 대해서는 그보다 작은 값들(0부터 arr[i]-1)로 끝나는 부분 수열 뒤에 현재 원소를 붙일 수 있습니다. 따라서 count[arr[i]]에 이전 카운트들을 모두 더하고, 자기 자신만으로 이루어진 새로운 수열 1개를 추가합니다.

예제 코드

#include<bits/stdc++.h>
using namespace std;

// 증가하는 부분 수열의 개수를 세는 함수
int count_sequence(int arr[], int n){
    int count[10] = {0};
    // 각 자릿수를 하나씩 확인
    for (int i = 0; i < n; i++){
        for (int j = arr[i] - 1; j >= 0; j--)
            count[arr[i]] += count[j];
        count[arr[i]]++;
    }
    // 가능한 모든 부분 수열의 총합 계산
    int result = 0;
    for (int i = 0; i < 10; i++)
        result += count[i];
    return result;
}

int main(){
    int arr[] = {3, 2, 4, 5, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << count_sequence(arr, n);
    return 0;
}

실행 결과

14

동작 과정 설명

입력 배열 {3, 2, 4, 5, 4}를 예로 들어 살펴보겠습니다.

순서대로 처리하면 다음과 같습니다.

- 3: count[3] = 1
- 2: count[2] = 1
- 4: count[4] = count[3] + count[2] + count[1] + count[0] + 1 = 3
- 5: count[5] = count[4] + count[3] + count[2] + ... + 1 = 7
- 4: count[4] = 3 + count[3] + count[2] + ... + 1 = 6

모든 값을 더하면 1 + 1 + 6 + 7 + ... 의 합으로 최종 결과 14가 나옵니다.

시간 복잡도

각 원소마다 최대 10개의 이전 카운트를 확인하므로 시간 복잡도는 O(n × 10), 즉 사실상 O(n)입니다. 공간 복잡도 역시 고정 크기의 카운트 배열만 사용하므로 O(1)입니다. 이는 완전 탐색으로 모든 부분 수열을 직접 생성하는 지수 시간 방식보다 훨씬 효율적입니다.