문제 개요
N×N 크기의 행렬이 주어졌을 때, M ≤ N이고 M ≥ 1인 조건을 만족하는 M×M 크기의 부분 행렬 중에서 모든 원소의 합이 최대가 되는 부분 행렬을 찾아 출력하는 것이 목표입니다. 입력 행렬에는 0, 양수, 음수를 포함한 임의의 정수 값이 사용될 수 있습니다.
예시
입력:
{{1, 1, 1, 1, 1},
{2, 2, 2, 2, 2},
{3, 3, 3, 3, 3},
{4, 4, 4, 4, 4},
{5, 5, 5, 5, 5}}
출력:
4 4
5 5
접근 방법
가장 단순한 방법은 전체 N×N 행렬에서 가능한 모든 M×M 부분 행렬을 하나씩 탐색하고 각각의 합을 계산한 뒤, 그중 합이 가장 큰 부분 행렬을 출력하는 것입니다. 이 방법은 이해하기 쉽지만 O(N²·M²)의 시간 복잡도가 필요하기 때문에, 더 적은 시간 복잡도로 문제를 해결할 수 있는 방법을 찾아야 합니다.
여기서는 슬라이딩 윈도우(sliding window) 기법을 활용합니다. 먼저 각 열마다 세로 방향으로 k개 원소의 합을 미리 계산해 저장해 둔 후, 가로 방향으로 윈도우를 한 칸씩 이동하면서 새로 들어오는 열의 합을 더하고 빠져나가는 열의 합을 빼는 방식으로 부분 행렬의 합을 상수 시간에 갱신할 수 있습니다. 덕분에 전체 연산량을 대략 O(N²) 수준까지 줄일 수 있습니다.
알고리즘
시작
1단계 → 함수 void matrix(int arr[][size], int k) 선언
IF k > size
Return
int array[size][size] 선언
FOR j = 0 ~ size-1
sum = 0
FOR i = 0 ~ k-1
sum = sum + arr[i][j]
array[0][j] = sum
FOR i = 1 ~ size-k
sum = sum + (arr[i+k-1][j] - arr[i-1][j])
array[i][j] = sum
maxsum = INT_MIN, pos = NULL 초기화
FOR i = 0 ~ size-k
sum = 0
FOR j = 0 ~ k-1
sum += array[i][j]
IF sum > maxsum
maxsum = sum
pos = &(arr[i][0])
FOR j = 1 ~ size-k
sum += (array[i][j+k-1] - array[i][j-1])
IF sum > maxsum
maxsum = sum
pos = &(arr[i][j])
FOR i = 0 ~ k-1
FOR j = 0 ~ k-1
*(pos + i*size + j) 값 출력
줄바꿈 출력
2단계 → main() 함수
int array[size][size] = {{1, 1, 1, 1, 1}, {2, 2, 2, 2, 2}, {3, 3, 3, 3, 3}, {4, 4, 4, 4, 4}, {5, 5, 5, 5, 5}} 선언
int k = 2 선언
matrix(array, k) 호출
종료
구현 코드
#include <bits/stdc++.h>
using namespace std;
#define size 5
void matrix(int arr[][size], int k){
if (k > size) return;
int array[size][size];
for (int j=0; j<size; j++){
int sum = 0;
for (int i=0; i<k; i++)
sum += arr[i][j];
array[0][j] = sum;
for (int i=1; i<size-k+1; i++){
sum += (arr[i+k-1][j] - arr[i-1][j]);
array[i][j] = sum;
}
}
int maxsum = INT_MIN, *pos = NULL;
for (int i=0; i<size-k+1; i++){
int sum = 0;
for (int j = 0; j<k; j++)
sum += array[i][j];
if (sum > maxsum){
maxsum = sum;
pos = &(arr[i][0]);
}
for (int j=1; j<size-k+1; j++){
sum += (array[i][j+k-1] - array[i][j-1]);
if (sum > maxsum){
maxsum = sum;
pos = &(arr[i][j]);
}
}
}
for (int i=0; i<k; i++){
for (int j=0; j<k; j++)
cout << *(pos + i*size + j) << " ";
cout << endl;
}
}
int main(){
int array[size][size] = {
{1, 1, 1, 1, 1},
{2, 2, 2, 2, 2},
{3, 3, 3, 3, 3},
{4, 4, 4, 4, 4},
{5, 5, 5, 5, 5},
};
int k = 2;
matrix(array, k);
return 0;
}
실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
4 4 5 5
핵심 정리
- 각 열의 세로 방향 k칸 누적합을 미리 계산해 두면 세로 윈도우의 합을 O(1)에 구할 수 있습니다.
- 가로 방향으로 윈도우를 이동하면서 합을 갱신하고, 현재까지의 최댓값(maxsum)과 시작 위치(pos)를 기록합니다.
- 탐색이 끝나면 pos가 가리키는 위치부터 M×M 크기만큼의 원소를 순서대로 출력하면 최대 합 부분 행렬을 얻을 수 있습니다.