문제 개요
2차원 행렬(matrix)과 정수 k가 주어졌을 때, 행렬 안에서 임의의 직사각형 영역을 골라 그 합이 k보다 크지 않은 경우 중 가장 큰 값을 찾는 것이 이번 글의 목표입니다.
예를 들어 다음과 같은 행렬이 주어지고 k = 3이라고 가정해 보겠습니다.
| 1 | 0 | 1 |
| 0 | -3 | 2 |
초록색으로 표시된 두 칸(각 행의 마지막 열)의 합은 1 + 2 = 3이므로, 정답은 3이 됩니다.
접근 방법
이 문제는 열 구간 고정 → 행별 누적 합(prefix sum) → set을 이용한 이진 탐색의 순서로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 직사각형의 왼쪽 경계 l과 오른쪽 경계 r을 고정하면, 2차원 문제가 각 행의 해당 구간 합을 담은 1차원 배열(rowSum) 문제로 바뀝니다.
- rowSum의 누적합 currSum을 계산할 때, 과거의 어떤 누적합 prev에 대해 currSum − prev ≤ k를 만족하면서 그 차이가 최대가 되려면, prev는 반드시 'currSum − k 이상인 값 중 최솟값'이어야 합니다.
- std::set의 lower_bound()를 사용하면 이러한 값을 O(log n) 만에 찾을 수 있습니다.
알고리즘 단계
- maxSumSubmatrix() 함수가 2차원 배열 matrix와 정수 k를 입력받습니다.
- n := 행의 개수, m := 열의 개수로 설정하고, ans := −∞로 초기화합니다.
- l := 0부터 m − 1까지 반복합니다.
- 크기가 n인 배열 rowSum을 선언합니다.
- r := l부터 m − 1까지 반복합니다.
- i := 0부터 n − 1까지 반복하며 rowSum[i] += matrix[i][r]로 갱신합니다.
- 정수 집합(set) s를 선언하고 0을 삽입한 뒤, currSum := 0으로 초기화합니다.
- i := 0부터 n − 1까지 반복합니다.
- currSum += rowSum[i]
- it := s에서 currSum − k보다 작지 않은(이상인) 첫 번째 원소
- it가 s의 끝이 아니라면 ans := max(ans, currSum − *it)
- s에 currSum을 삽입합니다.
- ans를 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxSumSubmatrix(vector<vector<int>>& matrix, int k) {
int n = matrix.size();
int m = matrix[0].size();
int ans = INT_MIN;
for(int l = 0; l < m; l++){
vector <int> rowSum(n);
for(int r = l; r < m; r++){
for(int i = 0; i < n; i++)rowSum[i] += matrix[i][r];
set < int > s;
s.insert(0);
int currSum = 0;
for(int i = 0; i < n; i++){
currSum += rowSum[i];
set <int> :: iterator it = s.lower_bound(currSum - k);
if(it != s.end()){
ans = max(ans, (currSum - *it));
}
s.insert(currSum);
}
}
}
return ans;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,0,1},{0,-3,2}};
cout << (ob.maxSumSubmatrix(v, 3));
}
입력
[{1,0,1},{0,-3,2}]
3
출력
3
시간 복잡도 분석
모든 열 쌍(l, r)을 검사하는 데 O(m²)이 소요되고, 각 열 쌍마다 행의 개수만큼 set 연산(O(log n))이 수행되므로 전체 시간 복잡도는 O(m² · n log n)입니다. 추가로 필요한 공간은 rowSum 배열과 set 저장에 비례하여 O(n) 수준입니다.