이 튜토리얼에서는 크기가 3인 증가하는 부분 수열의 최대 곱을 구하는 프로그램을 살펴보겠습니다.
양의 정수로 이루어진 배열이 주어졌을 때, 세 개의 원소를 인덱스 순서대로 선택하여 값이 점점 커지는(증가하는) 부분 수열을 만들고, 그중 곱이 가장 큰 조합을 찾는 것이 목표입니다.
문제 이해하기
예를 들어 배열이 [10, 11, 9, 5, 6, 1, 20]이라면, 가능한 증가 부분 수열 중 곱이 가장 큰 것은 10, 11, 20입니다. 이 세 값의 곱은 10 × 11 × 20 = 2200이 됩니다.
접근 방법
모든 세 원소 조합을 일일이 확인하면 O(n³)의 시간이 걸려 비효율적입니다. 대신 아래 두 단계로 나누면 O(n log n)에 문제를 해결할 수 있습니다.
- 왼쪽의 더 작은 값 미리 계산: set(균형 이진 탐색 트리)에 원소를 하나씩 삽입하면서, 각 위치 기준 왼쪽에 있는 값들 중 자신보다 작으면서 가장 큰 값을 저장해 둡니다.
- 오른쪽의 최댓값 추적: 배열을 오른쪽에서 왼쪽으로 순회하며, 현재 위치보다 오른쪽에 있는 원소들의 최댓값을 유지합니다.
각 위치 i를 가운데 원소로 삼을 때 만들 수 있는 증가 부분 수열의 곱은 "왼쪽의 작은 값 × arr[i] × 오른쪽의 최댓값"이 되며, 이 값들을 모두 비교해 최댓값을 구합니다.
C++ 구현 예제
#include<bits/stdc++.h>
using namespace std;
//부분 수열의 최대 곱을 반환하는 함수
long long int maxProduct(int arr[] , int n) {
int smaller[n];
smaller[0] = -1;
set<int>S;
for (int i = 0; i < n ; i++) {
auto j = S.insert(arr[i]);
auto itc = j.first;
--itc;
if (itc != S.end())
smaller[i] = *itc;
else
smaller[i] = -1;
}
long long int result = INT_MIN;
int max_right = arr[n-1];
for (int i=n-2 ; i >= 1; i--) {
if (arr[i] > max_right)
max_right = arr[i];
else if (smaller[i] != -1)
result = max(smaller[i] * arr[i] * max_right, result);
}
return result;
}
int main() {
int arr[] = {10, 11, 9, 5, 6, 1, 20};
int n = sizeof(arr)/sizeof(arr[0]);
cout << maxProduct(arr, n) << endl;
return 0;
}
실행 결과
2200
코드 핵심 정리
- smaller[i]: i번째 원소보다 왼쪽에 있으면서 값이 작은 원소 중 최댓값 (없으면 -1)
- max_right: 현재 위치보다 오른쪽에 있는 원소들의 최댓값
- result: 지금까지 확인한 증가 부분 수열 곱의 최댓값
set의 삽입과 탐색에 로그 시간이 걸리므로 전체 시간 복잡도는 O(n log n), 추가 배열 사용으로 공간 복잡도는 O(n)입니다. 왼쪽 정보와 오른쪽 정보를 각각 한 번의 순회로 구해내기 때문에 입력 크기가 커져도 안정적인 성능을 기대할 수 있습니다.