문제 개요
이 문제에서는 배열 arr[]이 주어지며, 우리의 목표는 배열에서 곱이 최대가 되는 4개 원소 조합(크기 4의 부분 수열, 쿼드러플)을 찾는 프로그램을 C++로 작성하는 것입니다.
문제 설명 — 주어진 배열에서 네 개의 원소를 선택했을 때 그 곱이 최대가 되는 조합을 찾아야 합니다.
예시를 통해 문제를 자세히 살펴보겠습니다.
입력
arr[] = {4, -2, 5, -6, 8}
출력
480
설명
네 원소 (-6, -2, 5, 8)를 선택했을 때 곱이 480이 되어, 가능한 모든 조합 중 가장 큰 값을 얻습니다.
해결 접근 방식
이 문제는 여러 가지 방법으로 해결할 수 있습니다.
방법 1: 완전 탐색(Brute Force)
가장 단순한 방법은 배열을 직접 순회하면서 가능한 모든 4개 원소 조합을 찾고, 각 조합의 곱을 계산한 뒤 서로 비교하여 최대 곱을 구하는 것입니다.
풀이 동작을 보여주는 프로그램:
#include <iostream>
using namespace std;
int max(int a, int b){
if(a > b)
return a;
return b;
}
int findMaxProdQuad(int arr[], int n){
int maxProd = 0;
int prod = 1;
for (int i = 0; i <= n - 4; i++)
for (int j = i + 1; j <= n - 3; j++)
for (int k = j + 1; k <= n - 2; k++)
for (int l = k + 1; l <= n - 1; l++) {
prod = arr[i] * arr[j] * arr[k] * arr[l];
maxProd = max(maxProd, prod);
prod = 1;
}
return maxProd;
}
int main(){
int arr[] = {4, -2, 5, -6, 8};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Maximum product of quadruple is "<<findMaxProdQuad(arr, n);
return 0;
}
출력
Maximum product of quadruple is 480
이 방법은 네 개의 중첩 반복문을 사용하므로 시간 복잡도가 O(n⁴)입니다. 배열의 크기가 커질수록 실행 시간이 급격히 증가한다는 단점이 있습니다.
방법 2: 상위 4개 최댓값과 하위 4개 최솟값 활용
최대 곱 쿼드러플을 찾는 더 효율적인 방법은 배열에서 가장 큰 네 개의 원소와 가장 작은 네 개의 원소를 찾는 것입니다.
배열의 첫 네 개 최댓값을 mx1, mx2, mx3, mx4라 하고, 첫 네 개 최솟값을 mn1, mn2, mn3, mn4라고 합시다. 그러면 다음 세 가지 곱 중 하나가 정답이 됩니다.
1. mx1 * mx2 * mx3 * mx4 (네 개의 큰 양수 조합) 2. mn1 * mn2 * mn3 * mn4 (절댓값이 큰 음수 네 개의 조합) 3. mx1 * mx2 * mn1 * mn2 (큰 양수 두 개 + 절댓값이 큰 음수 두 개)
이 세 값 중 최댓값을 반환하면 최대 곱 쿼드러플을 구할 수 있으며, 음수가 포함된 경우까지 모든 경우의 수가 고려됩니다.
알고리즘 구현을 보여주는 프로그램:
#include <iostream>
using namespace std;
int max(int a, int b){
if(a > b)
return a;
return b;
}
int findMaxProdQuad(int arr[], int n) {
int mx1 = -1000, mx2 = -1000, mx3 = -10000, mx4 = -1000;
int mn1 = 1000, mn2 = 1000, mn3 = 1000, mn4 = 1000;
for (int i = 0; i < n; i++) {
if(arr[i] < mn1){
mn4 = mn3;
mn3 = mn2;
mn2 = mn1;
mn1 = arr[i];
}
else if(arr[i] < mn2){
mn4 = mn3;
mn3 = mn2;
mn2 = arr[i];
}
else if(arr[i] < mn3){
mn4 = mn3;
mn3 = arr[i];
}
else if(arr[i] < mn4){
mn4 = arr[i];
}
if(arr[i] > mx1){
mx4 = mx3;
mx3 = mx2;
mx2 = mx1;
mx1 = arr[i];
}
else if(arr[i] > mx2){
mx4 = mx3;
mx3 = mx2;
mx2 = arr[i];
}
else if(arr[i] > mx3){
mx4 = mx3;
mx3 = arr[i];
}
else if(arr[i] > mx4){
mx4 = arr[i];
}
}
int maxVal = max ((mx1 * mx2 * mx3 * mx4), (mn1 * mn2 * mn3 * mn4));
maxVal = max(maxVal, (mx1 * mx2 * mn1 * mn2));
return maxVal;
}
int main() {
int arr[] = {4, -2, 5, -6, 8};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Maximum product of quadruple is "<<findMaxProdQuad(arr, n);
return 0;
}
출력
Maximum product of quadruple is 480
이 방법은 배열을 한 번만 순회하면 되므로 시간 복잡도가 O(n)으로 매우 효율적입니다.
방법 3: 정렬 활용
배열을 먼저 정렬하는 방법도 있습니다. 정렬이 완료되면 네 개의 최댓값과 최솟값은 각각 배열의 뒷부분과 앞부분에 위치하게 됩니다. 이후 앞선 방법과 마찬가지로 최댓값·최솟값 조합 세 가지의 곱을 비교하여 최댓값을 구하면 됩니다.
접근 방식 구현을 보여주는 프로그램:
#include <bits/stdc++.h>
using namespace std;
int findMaxProdQuad(int arr[], int n){
sort(arr, arr + n);
int maxVal = max((arr[n-1] * arr[n-2] * arr[n-3] * arr[n-4]), (arr[0] *
arr[1] * arr[2] * arr[3]));
maxVal = max(maxVal, (arr[n-1] * arr[n-2] * arr[0] * arr[1]));
return maxVal;
}
int main(){
int arr[] = {4, -2, 5, -6, 8};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"Maximum product of quadruple is "<<findMaxProdQuad(arr, n);
return 0;
}
출력
Maximum product of quadruple is 480
정렬 기반 방법의 시간 복잡도는 O(n log n)입니다. 완전 탐색(O(n⁴))보다는 훨씬 빠르지만, 방법 2(O(n))보다는 다소 느립니다.
마무리
정리하면, 배열에서 곱이 최대가 되는 4개 원소 조합은 완전 탐색(O(n⁴)), 상위 최댓값·하위 최솟값 추적(O(n)), 정렬(O(n log n)) 세 가지 방법으로 구할 수 있습니다. 입력 크기와 성능 요구 사항에 맞게 적절한 방법을 선택하는 것이 좋습니다.