이번 튜토리얼에서는 두 배열의 곱의 최대 합(Maximum Sum of Products)을 구하는 프로그램을 C++로 작성해 보겠습니다.
문제 이해하기
크기가 같은 두 개의 배열이 주어집니다. 첫 번째 배열의 원소와 두 번째 배열의 원소를 하나씩 짝지어 곱한 뒤, 그 곱들을 모두 더했을 때 가장 커지는 합을 찾는 것이 목표입니다.
예를 들어 배열 A = {1, 2, 3}, 배열 B = {4, 5, 1}이 주어졌다면, 두 배열의 원소를 어떻게 짝지느냐에 따라 결과가 달라지므로 합을 최대화하는 짝짓기를 찾아야 합니다.
접근 방법
핵심 아이디어는 아주 간단합니다. 두 배열을 모두 오름차순으로 정렬한 뒤, 같은 인덱스의 원소끼리 곱하면 됩니다.
이 방식이 최적이 되는 이유는 재배열 부등식(rearrangement inequality) 덕분입니다. 두 수열을 같은 순서로 정렬했을 때 대응 원소끼리 곱한 합이 가능한 모든 짝짓기 중에서 가장 큽니다. 큰 수는 큰 수와, 작은 수는 작은 수와 곱해야 합을 극대화할 수 있습니다. 음수가 포함된 경우에도 마찬가지인데, 음수끼리 곱하면 양수가 되므로 같은 순서 정렬이 항상 최적의 답을 보장합니다.
C++ 구현
#include <bits/stdc++.h>
using namespace std;
// 두 배열을 정렬한 뒤 원소끼리 곱하여 최대 합을 계산하는 함수
int maximumSOP(int a[], int b[], int n) {
int sop = 0;
// 두 배열을 오름차순으로 정렬
sort(a, a + n);
sort(b, b + n);
// 같은 인덱스의 원소를 곱하여 누적
for (int i = 0; i < n; i++) {
sop += a[i] * b[i];
}
return sop;
}
int main() {
int A[] = { 1, 2, 3 };
int B[] = { 4, 5, 1 };
int n = sizeof(A) / sizeof(A[0]);
cout << maximumSOP(A, B, n);
return 0;
}
출력
24
동작 원리
배열 A를 정렬하면 {1, 2, 3}이 되고, 배열 B를 정렬하면 {1, 4, 5}가 됩니다. 같은 인덱스의 원소끼리 곱하면 다음과 같습니다.
- 1 × 1 = 1
- 2 × 4 = 8
- 3 × 5 = 15
따라서 최대 합은 1 + 8 + 15 = 24입니다.
참고로, 배열을 함수에 포인터 형태로 전달하면 함수 내부에서 sizeof 연산자로 배열의 실제 크기를 알아낼 수 없습니다. 그래서 위 코드에서는 main 함수에서 배열 크기를 계산한 후 매개변수 n으로 함께 전달하는 방식을 사용했습니다. 이렇게 하면 배열의 길이와 무관하게 안전하게 동작합니다.
시간 복잡도
두 배열을 각각 정렬하는 데 O(n log n)의 시간이 소요되며, 곱셈과 합산을 수행하는 반복문에는 O(n)이 걸립니다. 따라서 전체 시간 복잡도는 O(n log n)입니다. 제자리(in-place) 정렬을 사용하므로 추가 공간 복잡도는 O(1)입니다.