이 문제에서는 배열 arr[]과 Q개의 쿼리가 주어집니다. 각 쿼리는 다음 두 가지 유형 중 하나입니다.
- 유형 1: 주어진 범위 [Start ~ End] 내에서 최대 곱(maximum product pair)을 찾습니다.
- 유형 2: i번째 인덱스의 요소를 지정된 값으로 업데이트합니다.
즉, 우리의 목표는 요소 업데이트가 중간에 발생하더라도 특정 범위 내에서 최대 곱 쌍을 정확하게 찾아내는 프로그램을 C++로 작성하는 것입니다.
문제 이해를 위한 예시
입력:
arr = {4, 2, 6, 9, 1}
Q = 3
Q1 = [1, 1, 4]
Q2 = [2, 2, 3]
Q3 = [1, 0, 2]출력: 54, 12
설명
쿼리 1(유형 1): 범위 = {2, 6, 9, 1}. 최대 곱은 6 × 9 = 54
쿼리 2(유형 2): i = 2를 값 3으로 업데이트 → 배열은 {4, 2, 3, 9, 1}이 됩니다.
쿼리 3(유형 1): 범위 = {4, 2, 3}. 최대 곱은 4 × 3 = 12
해결 방법 1: 브루트 포스(Brute Force) 접근
가장 단순한 방법은 유형 1의 쿼리가 들어올 때마다 해당 범위의 전체 배열을 순회하면서 가능한 모든 쌍의 곱을 계산하고, 그중 최댓값을 찾는 것입니다.
코드 예제
#include <iostream>
using namespace std;
int max(int a, int b){
if(a>b)
return a;
return b;
}
int findMaxProductPair(int arr[], int n, int start, int end){
int maxProd = 0;
for(int i = start; i <= end; i++){
for(int j = i+1; j <= end; j++){
maxProd = max(maxProd, (arr[i]*arr[j]));
}
}
return maxProd;
}
int main(){
int arr[] = {4, 2, 6, 9, 1, 5};
int n = 6;
int Q = 3;
int query[Q][3] = {{1, 1, 4}, {2, 2, 3}, {1, 0, 2}};
for(int i = 0; i < Q; i++){
if(query[i][0] == 1){
cout<<"The maximum product pair in the range is "<<findMaxProductPair(arr, n, query[i][1], query[i][2])<<"\n";
}
else if(query[i][0] == 2){
cout<<"Updating values...\n";
arr[query[i][1]] = query[i][2];
}
}
return 0;
}
실행 결과
The maximum product pair in the range is 54
Updating values...
The maximum product pair in the range is 12
이 방법은 직관적이고 구현이 간단하지만, 쿼리 하나를 처리할 때마다 범위 내 모든 쌍을 검사해야 하므로 시간 복잡도가 O(Q × N²)에 달합니다. 배열의 크기나 쿼리 수가 커지면 성능이 급격히 저하됩니다.
해결 방법 2: 세그먼트 트리(Segment Tree)를 활용한 효율적 접근
더 효율적인 해결책은 세그먼트 트리 자료구조를 사용하는 것입니다. 각 노드에 해당 구간의 최댓값(maxEle)과 두 번째 최댓값(secMax)을 함께 저장하면, 범위 내 최대 곱 쌍은 단순히 이 두 값의 곱으로 구할 수 있습니다.
이렇게 하면 쿼리 처리와 값 업데이트 모두 O(log N) 시간에 수행할 수 있어, 전체 시간 복잡도는 O(N + Q log N)으로 크게 개선됩니다.
코드 예제
#include <iostream>
using namespace std;
struct segment {
int maxEle;
int secMax;
};
segment findMaxProductPair(segment* prodTree, int index, int start, int end, int L, int R) {
segment result;
result.maxEle = -1;
result.secMax = -1;
if (L > end || R < start || start > end)
return result;
if (start >= L && end <= R)
return prodTree[index];
int middleIndex = (start + end) / 2;
segment left = findMaxProductPair(prodTree, 2 * index, start,middleIndex, L, R);
segment right = findMaxProductPair(prodTree, 2 * index + 1,middleIndex + 1, end, L, R);
result.maxEle = max(left.maxEle, right.maxEle);
result.secMax = min(max(left.maxEle, right.secMax),max(right.maxEle, left.secMax));
return result;
}
void update(segment* prodTree, int index, int start, int end, int i, int updateVal) {
if (i < start || i > end)
return;
if (start == end) {
prodTree[index].maxEle = updateVal;
prodTree[index].secMax = -1;
return;
}
int middleIndex = (start + end) / 2;
update(prodTree, 2 * index, start, middleIndex, i, updateVal);
update(prodTree, 2 * index + 1, middleIndex + 1, end, i, updateVal);
prodTree[index].maxEle = max(prodTree[2 * index].maxEle,prodTree[2 * index + 1].maxEle);
prodTree[index].secMax = min(max(prodTree[2 * index].maxEle,prodTree[2 * index + 1].secMax), max(prodTree[2 * index + 1].maxEle,prodTree[2 * index].secMax));
}
void buildtree(segment* prodTree, int* arr, int index, int start, int end) {
if (start > end) {
return;
}
if (start == end) {
prodTree[index].maxEle = arr[start];
prodTree[index].secMax = -1;
return;
}
int middleIndex = (start + end) / 2;
buildtree(prodTree, arr, 2 * index, start, middleIndex);
buildtree(prodTree, arr, 2 * index + 1, middleIndex + 1, end);
int maximum = max(prodTree[2 * index].maxEle, prodTree[2 * index + 1].maxEle);
int secMaximum = min(max(prodTree[2 * index].maxEle, prodTree[2 * index + 1].secMax),max(prodTree[2 * index + 1].maxEle, prodTree[2 * index].secMax));
prodTree[index].maxEle = maximum;
prodTree[index].secMax = secMaximum;
}
int main() {
int arr[] = {4, 2, 6, 9, 1, 5};
int n = 6;
int Q = 3;
segment* prodTree = new segment[4 * n + 1];
buildtree(prodTree, arr, 1, 0, n - 1);
int query[Q][3] = {{1, 1, 4}, {2, 2, 3}, {1, 0, 2}};
for(int i = 0; i < Q; i++){
if(query[i][0] == 1){
segment result = findMaxProductPair(prodTree, 1, 0, n - 1,query[i][1] , query[i][2]);
cout<<"The maximum product pair in the range is "<<(result.maxEle*result.secMax)<<"\n";
}
else if(query[i][0] == 2){
cout<<"Updating values...\n";
update(prodTree, 1, 0, n - 1, query[i][1], query[i][2]);
}
}
return 0;
}
실행 결과
The maximum product pair in the range is 54
Updating values...
The maximum product pair in the range is 12
정리
두 접근 방식 모두 동일한 결과를 출력하지만, 성능 면에서는 확연한 차이가 있습니다.
- 브루트 포스: 구현이 간단하지만 쿼리당 O(N²)의 시간이 소요되어 대규모 입력에는 부적합합니다.
- 세그먼트 트리: 초기 트리 구축에 O(N), 각 쿼리와 업데이트에 O(log N)이 소요되어 실시간 업데이트가 빈번한 환경에서 훨씬 효율적입니다.
배열 요소가 자주 변경되면서 범위 기반 질의가 반복되는 상황이라면, 세그먼트 트리처럼 구간 정보를 계층적으로 관리하는 자료구조를 활용하는 것이 바람직한 선택입니다.