C++로 정방 행렬(정사각 행렬)의 최댓값과 최솟값 구하기

이 글에서는 n×n 크기의 정방 행렬(정사각 행렬)이 주어졌을 때, 행렬 전체를 효율적으로 탐색하여 최댓값과 최솟값을 찾는 방법을 다룹니다.

문제 설명

n*n 차수의 정방 행렬이 주어졌을 때, 행렬에 포함된 요소들 중 최댓값과 최솟값을 구하는 것이 목표입니다.

예시

다음과 같은 행렬이 주어졌다고 가정해 보겠습니다.

{{15, 17, 19}, {5, 1, 7}, {14, 5, 16}}
결과:
최솟값은 1, 최댓값은 19입니다.

알고리즘

• 행렬의 각 행에서 한쪽 끝에 있는 요소와 반대쪽 끝에 있는 요소, 즉 두 개의 요소를 선택합니다.
• 선택한 두 요소를 서로 비교한 뒤, 더 작은 값은 현재까지의 최솟값과, 더 큰 값은 현재까지의 최댓값과 각각 비교합니다.
• 두 개의 요소를 비교하는 데 3번의 비교 연산이 필요하므로, 행렬 전체를 탐색할 때 총 3/2·n² 번의 비교만으로 최댓값과 최솟값을 구할 수 있습니다. 이는 모든 요소를 개별적으로 비교하는 방식보다 비교 횟수를 줄여주는 최적화된 접근 방식입니다.

구현 예제

위 알고리즘을 C++ 코드로 구현하면 다음과 같습니다.

#include <bits/stdc++.h>
#define MAX 200
using namespace std;

void getMinMax(int matrix[MAX][MAX], int n) {
   int min = INT_MAX;
   int max = INT_MIN;
   for (int i = 0; i < n; ++i) {
      for (int j = 0; j <= n / 2; ++j) {
         if (matrix[i][j] > matrix[i][n - j - 1]) {
            if (min > matrix[i][n - j - 1]) {
               min = matrix[i][n - j - 1];
            }
            if (max < matrix[i][j]) {
               max = matrix[i][j];
            }
         } else {
            if (min > matrix[i][j]) {
               min = matrix[i][j];
            }
            if (max < matrix[i][n - j - 1]) {
               max = matrix[i][n - j - 1];
            }
         }
      }
   }
   cout << "Maximum = " << max << ", Minimum = " << min << endl;
}

int main() {
   int matrix[MAX][MAX] = { {15, 17, 19}, {5, 1, 7}, {14, 5, 16} };
   getMinMax(matrix, 3);
   return 0;
}

출력 결과

Maximum = 19, Minimum = 1

동작 원리 정리

이 코드는 각 행의 앞쪽 요소 matrix[i][j]와 뒤쪽 요소 matrix[i][n-j-1]를 짝지어 비교합니다. 두 값 중 큰 값을 후보 최댓값으로, 작은 값을 후보 최솟값으로 처리함으로써 한 번의 순회로 두 값을 동시에 갱신합니다. 초기값은 각각 INT_MIN(최댓값용)과 INT_MAX(최솟값용)로 설정되어 있어 어떤 입력 값이 들어와도 올바르게 갱신됩니다.