문제 개요
이 문제에서는 크기가 n인 배열 arr[]와 정수 m이 주어집니다. 우리의 과제는 주어진 배열에서 부분 배열 평균들의 평균(mean of subarray means)을 구하는 것입니다.
문제 설명 − 즉, 크기가 m인 각 부분 배열(subarray)의 평균을 먼저 구한 뒤, 이 평균값들을 다시 평균 내어 최종 결과를 반환해야 합니다.
예제를 통해 문제를 이해해 보겠습니다.
입력
arr[] = {2, 5, 3, 6, 1}, m = 3출력
3.78
설명
크기가 m인 모든 부분 배열: {2, 5, 3}, {5, 3, 6}, {3, 6, 1}크기 m인 부분 배열 평균들의 평균은 다음과 같이 계산됩니다.
$$\frac{\left(\frac{2+5+3}{3}\right)+\left(\frac{5+3+6}{3}\right)+\left(\frac{3+6+1}{3}\right)}{3}=\frac{\frac{10}{3}+\frac{14}{3}+\frac{10}{3}}{3}=\frac{34}{9}\approx 3.78$$
풀이 접근 방법
가장 단순한 해결 방법은 크기가 m인 모든 부분 배열을 일일이 찾아 각각의 평균을 계산하는 것입니다. 그런 다음 모든 평균을 더하고 부분 배열의 개수로 나누면 결과를 얻을 수 있습니다. 하지만 이 방법은 매번 부분 배열의 합을 새로 계산해야 하므로 비효율적입니다.
더 효율적인 방법은 슬라이딩 윈도우(sliding window) 알고리즘을 활용하는 것입니다. 동작 과정은 다음과 같습니다.
- 인덱스 0부터 시작하는 크기 m의 첫 번째 윈도우(부분 배열)의 합을 구합니다.
- 윈도우를 한 칸씩 오른쪽으로 이동하면서, 빠져나가는 요소는 빼고 새로 들어오는 요소는 더해 윈도우의 합을 O(1)에 갱신합니다.
- 각 윈도우마다 평균(윈도우 합 ÷ m)을 구해 누적합니다.
- 마지막에 누적된 평균의 합을 윈도우 개수(n − m + 1)로 나누어 반환합니다.
이 방법의 시간 복잡도는 O(n), 공간 복잡도는 O(1)로, 전체 배열을 한 번만 순회하면서 답을 구할 수 있습니다.
구현 예제
위에서 설명한 솔루션의 동작을 보여주는 프로그램입니다.
#include <iostream>
using namespace std;
// 크기 m인 부분 배열 평균들의 평균을 계산하는 함수
float calcMeanOfSubarrayMeans(int arr[], int n, int m) {
float meanSum = 0, windowSum = 0;
// 첫 번째 윈도우의 합 계산
for (int i = 0; i < m; i++)
windowSum += arr[i];
meanSum += (windowSum / m);
// 슬라이딩 윈도우로 나머지 윈도우 처리
for (int i = m; i < n; i++) {
windowSum = windowSum - arr[i - m] + arr[i];
meanSum += (windowSum / m);
}
int windowCount = n - m + 1;
return (meanSum / windowCount);
}
int main() {
int arr[] = { 2, 5, 3, 6, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
int m = 3;
cout << "부분 배열 평균들의 평균은 " << calcMeanOfSubarrayMeans(arr, n, m);
return 0;
}
출력
부분 배열 평균들의 평균은 3.77778
정리
슬라이딩 윈도우 기법을 사용하면 각 부분 배열의 합을 반복적으로 다시 계산하지 않고도 이전 값을 재활용할 수 있어, 크기가 m인 모든 부분 배열의 평균과 그 평균의 평균을 선형 시간 안에 효율적으로 구할 수 있습니다.