문제 소개
크기가 n×n인 2차원 배열(행렬)이 주어졌을 때, 행렬에 포함된 모든 원소의 평균(mean)과 중앙값(median)을 출력하는 C++ 프로그램을 작성하는 것이 이번 문제의 목표입니다.
평균(Mean)이란?
평균은 데이터 집합 전체를 대표하는 값으로, 행렬에서는 행렬을 구성하는 모든 원소 값의 산술 평균을 의미합니다.
평균 = (행렬의 모든 원소의 합) ÷ (행렬의 원소 총개수)
n×n 행렬이라면 원소의 총개수는 n²이므로, 모든 원소를 한 번씩 더한 뒤 n²로 나누면 됩니다.
중앙값(Median)이란?
중앙값은 데이터를 크기순으로 정렬했을 때 정확히 가운데에 위치하는 값입니다. 따라서 중앙값을 구하려면 행렬의 원소들을 먼저 정렬해야 합니다.
정렬된 상태에서 중앙값은 다음과 같이 계산할 수 있습니다.
- n이 홀수인 경우: median = matrix[n/2][n/2]
- n이 짝수인 경우: median = ((matrix[(n-2)/2][n-1]) + (matrix[n/2][0])) ÷ 2
위 공식은 행렬의 원소들이 행 우선(row-major) 순서로 오름차순 정렬되어 있을 때 그대로 적용됩니다. 만약 정렬되어 있지 않다면, 먼저 행렬을 1차원 배열로 펼쳐 정렬한 후 같은 방식으로 가운데 값을 찾아야 합니다.
예제 코드
아래는 위 풀이 과정을 구현한 C++ 프로그램입니다.
#include <iostream>
using namespace std;
const int N = 4;
// 행렬의 평균을 계산하는 함수
int calcMean(int Matrix[][N]) {
int sum = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
sum += Matrix[i][j];
return (int)sum / (N * N);
}
// 행렬의 중앙값을 계산하는 함수
int calcMedian(int Matrix[][N]) {
if (N % 2 != 0)
return Matrix[N / 2][N / 2];
if (N % 2 == 0)
return (Matrix[(N - 2) / 2][N - 1] + Matrix[N / 2][0]) / 2;
}
int main() {
int Matrix[N][N] = {
{5, 10, 15, 20},
{25, 30, 35, 40},
{45, 50, 55, 60},
{65, 70, 75, 80}};
cout << "Mean of the matrix: " << calcMean(Matrix) << endl;
cout << "Median of the matrix : " << calcMedian(Matrix) << endl;
return 0;
}
실행 결과
Mean of the matrix: 42 Median of the matrix : 42
코드 설명
- calcMean(): 이중 반복문으로 행렬의 모든 원소를 순회하며 합계를 구한 뒤, 원소 개수(N×N)로 나누어 평균을 반환합니다.
- calcMedian(): N의 홀짝 여부에 따라 중앙 위치의 원소 하나 또는 가운데 두 원소의 평균을 반환합니다. 예제의 행렬은 이미 오름차순으로 정렬되어 있으므로 별도의 정렬 과정 없이 인덱스로 바로 접근할 수 있습니다.
예제 행렬의 원소 합은 680이고 원소 개수는 16이므로, 평균은 680 ÷ 16 = 42가 됩니다. 중앙값 역시 가운데 두 원소인 40과 45의 평균으로 계산되어 42가 출력됩니다.
시간 복잡도는 평균 계산 시 O(n²)이며, 정렬이 필요한 경우에는 추가로 O(n² log n²)의 비용이 발생합니다.