크기가 각각 m과 n인 두 개의 양의 정수 배열이 있다고 가정해 보겠습니다(단, m > n). 우리는 두 번째 배열에 0을 삽입하여 두 배열의 내적(dot product)을 최대화해야 하며, 이때 주어진 배열의 원소 순서는 절대 변경할 수 없다는 점에 유의해야 합니다.
예를 들어 배열 A = [2, 3, 1, 7, 8], 배열 B = [3, 6, 7]이 있다고 합시다. 두 번째 배열의 첫 번째와 세 번째 위치에 0을 삽입하면 내적은 다음과 같이 계산되어 최댓값 107을 얻을 수 있습니다.
2 × 0 + 3 × 3 + 1 × 0 + 7 × 6 + 8 × 7 = 107
즉, 0을 어느 위치에 배치하느냐에 따라 결과가 달라지므로, 최적의 배치를 찾는 것이 이 문제의 핵심입니다.
동적 계획법(Dynamic Programming)을 활용한 풀이
이 문제는 동적 계획법으로 효율적으로 해결할 수 있습니다. 배열 A의 크기를 m, 배열 B의 크기를 n이라 할 때, (n+1)×(m+1) 크기의 DP 테이블을 생성하고 모든 값을 0으로 초기화합니다. 그런 다음 아래 절차에 따라 테이블을 채워 나갑니다.
- i를 1부터 n까지 반복합니다.
- 각 i에 대해 j를 i부터 m까지 반복하면서 다음 점화식을 적용합니다.
table[i][j] = max(table[i-1][j-1] + A[j-1] * B[i-1], table[i][j-1])
여기서 table[i][j]는 배열 B의 앞 i개 원소를 사용하여 배열 A의 앞 j개 원소와 매칭했을 때 얻을 수 있는 최대 내적을 의미합니다. 현재 원소 쌍(A[j-1], B[i-1])을 곱해서 더하는 경우와, 해당 위치를 건너뛰고(0을 삽입하는 것과 동일) 이전 값을 유지하는 경우 중 더 큰 값을 선택하는 방식입니다. 최종적으로 table[n][m]에 저장된 값이 답이 됩니다.
C++ 구현 예제
#include <iostream>
using namespace std;
long long int findMaximumDotProd(int A[], int B[], int m, int n) {
long long int table[n+1][m+1];
for(int i = 0; i<=n; i++){
for(int j = 0; j<=m; j++){
table[i][j] = 0;
}
}
for (int i=1; i<=n; i++)
for (int j=i; j<=m; j++)
table[i][j] = max((table[i-1][j-1] + (A[j-1]*B[i-1])) , table[i][j-1]);
return table[n][m];
}
int main() {
int A[] = { 2, 3, 1, 7, 8 };
int B[] = { 3, 6, 7 };
int m = sizeof(A)/sizeof(A[0]);
int n = sizeof(B)/sizeof(B[0]);
cout << "Maximum dot product: " << findMaximumDotProd(A, B, m, n);
}실행 결과
Maximum dot product: 107
위 알고리즘의 시간 복잡도는 O(n×m), 공간 복잡도 역시 O(n×m)입니다. 완전 탐색으로 0을 삽입할 모든 위치 조합을 확인하는 것보다 훨씬 효율적으로 최적해를 구할 수 있다는 점이 이 접근 방식의 가장 큰 장점입니다.