C++ 행렬(Matrix)에서 최대 차이를 가지는 특정 쌍 찾기

문제 개요

정수로 이루어진 n × n 크기의 행렬 mat이 주어졌을 때, 모든 가능한 인덱스 조합에 대해 mat(c, d) − mat(a, b) 값의 최댓값을 구하는 문제입니다. 단, 인덱스 선택 시 반드시 c > a 그리고 d > b라는 조건을 만족해야 합니다.

예를 들어 다음과 같은 5 × 5 행렬이 있다고 가정해 보겠습니다.

이 경우 출력 결과는 18입니다. 그 이유는 mat[4][2] − mat[1][0] = 10 − (-8) = 18로, 이 조합이 가능한 모든 쌍 중에서 가장 큰 차이를 만들어내기 때문입니다.

접근 방법

모든 쌍을 일일이 비교하는 브루트 포스 방식은 O(n⁴)의 시간 복잡도를 가지므로 비효율적입니다. 대신 전처리(Preprocessing) 기법을 활용하면 O(n²) 시간 안에 문제를 해결할 수 있습니다.

핵심 아이디어는 다음과 같습니다.

• 보조 배열 arr_max[i][j]가 행렬의 (i, j) 위치부터 오른쪽 아래 끝점인 (n-1, n-1)까지 영역 내 원소들의 최댓값을 저장하도록 미리 계산합니다.
• 행렬을 오른쪽 아래에서부터 역순으로 순회하면서, 각 위치에서 arr_max[i+1][j+1] − matrix[i][j] 값을 계산하여 지금까지 발견한 최댓값을 계속 갱신합니다.
• 마지막으로 누적된 최댓값을 반환하면 됩니다.

이렇게 하면 각 칸을 한 번씩만 방문하면서도 정답을 구할 수 있어 효율적입니다.

C++ 구현 예제

#include<iostream>
#define N 5
using namespace std;

int findMaxValue(int matrix[][N]) {
    int maxValue = -99999;
    int arr_max[N][N];

    // 마지막 원소 초기화
    arr_max[N-1][N-1] = matrix[N-1][N-1];
    int max_val = matrix[N-1][N-1];

    // 마지막 행 처리
    for (int j = N - 2; j >= 0; j--) {
        if (matrix[N-1][j] > max_val)
            max_val = matrix[N - 1][j];
        arr_max[N-1][j] = max_val;
    }

    // 마지막 열 처리
    max_val = matrix[N - 1][N - 1];
    for (int i = N - 2; i >= 0; i--) {
        if (matrix[i][N - 1] > max_val)
            max_val = matrix[i][N - 1];
        arr_max[i][N - 1] = max_val;
    }

    // 나머지 행렬 순회하며 최대 차이 계산
    for (int i = N-2; i >= 0; i--) {
        for (int j = N-2; j >= 0; j--) {
            if (arr_max[i+1][j+1] - matrix[i][j] > maxValue)
                maxValue = arr_max[i + 1][j + 1] - matrix[i][j];
            arr_max[i][j] = max(matrix[i][j], max(arr_max[i][j + 1], arr_max[i + 1][j]));
        }
    }
    return maxValue;
}

int main() {
    int mat[N][N] = {
        { 1, 2, -1, -4, -20 },
        { -8, -3, 4, 2, 1 },
        { 3, 8, 6, 1, 3 },
        { -4, -1, 1, 7, -6 },
        { 0, -4, 10, -5, 1 }
    };
    cout << "Maximum Value is " << findMaxValue(mat);
}

실행 결과

Maximum Value is 18

정리

이 알고리즘은 보조 배열을 활용한 전처리를 통해 각 위치에서의 후방 최댓값을 빠르게 참조할 수 있게 합니다. 덕분에 단순 완전 탐색의 O(n⁴)에서 O(n²)으로 시간 복잡도를 크게 줄일 수 있으며, 추가 공간 역시 n × n 크기의 보조 배열 하나면 충분합니다. 행렬에서 두 원소 간 최대 차이를 구하는 유사한 문제(예: 주식 매매 최대 이익 문제의 2차원 확장)에 널리 응용될 수 있는 패턴입니다.