문제 소개
첫 번째 인자로 2차원 숫자 배열을, 두 번째 인자로 목표 합(target)을 받는 JavaScript 함수를 작성해야 합니다.
이 함수는 배열 안에서 만들 수 있는 모든 직사각형(연속된 부분 행렬) 중에서 합이 가장 크면서 목표 값보다 작거나 같은 직사각형을 찾고, 그 합을 반환해야 합니다.
예를 들어, 함수의 입력이 다음과 같다고 가정해 보겠습니다.
const arr = [
[1, 0, 1],
[0, -2, 3]
];
const num = 2;이 경우 원하는 출력은 다음과 같습니다.
const output = 2;
출력 설명
합이 정확히 2가 되는 직사각형은 다음과 같습니다.
[
[0, 1],
[-2, 3]
]이 부분 행렬의 합은 0 + 1 + (-2) + 3 = 2로 목표 값과 일치하므로, 이것이 문제의 정답이 됩니다.
접근 방법
이 문제는 행 쌍 고정 + 누적 배열(dp) 기법과 카데인 알고리즘(Kadane's Algorithm)을 조합하면 효율적으로 해결할 수 있습니다.
- 두 개의 행 경계(l, r)를 고정한 뒤, 해당 행 범위에 포함된 각 열의 합을 dp 배열에 누적합니다.
- 누적된 1차원 배열에 대해 카데인 알고리즘으로 최대 부분합을 구합니다.
- 구한 최대값이 num 이하라면 곧바로 정답 후보(maxSum)를 갱신합니다.
- num을 초과한다면, 모든 열 구간(c ~ d)의 합을 하나씩 검사하여 num 이하인 최댓값을 찾아 갱신합니다.
- 탐색 도중 합이 정확히 num이 되면 더 이상 살펴볼 필요가 없으므로 즉시 num을 반환해 최적화합니다.
예제 코드
const arr = [
[1, 0, 1],
[0, -2, 3]
];
const num = 2;
const maxSum = (arr = [], num = 1) => {
const rows = arr.length;
const cols = arr[0].length;
let maxSum = -Infinity;
for(let l = 0; l < rows; l++) {
const dp = Array(cols).fill(0);
for(let r = l; r < rows; r++) {
let sum = 0, max = -Infinity;
for(let c = 0; c < cols; c++) {
dp[c] += arr[r][c];
if(sum < 0) sum = 0;
sum += dp[c];
max = Math.max(max, sum);
}
if(max <= num) maxSum = Math.max(max, maxSum);
else {
max = -Infinity;
for(let c = 0; c < cols; c++) {
sum = 0;
for(let d = c; d < cols; d++) {
sum += dp[d];
if(sum <= num) max = Math.max(sum, max);
}
}
maxSum = Math.max(max, maxSum);
}
if(maxSum === num) return num;
}
}
return maxSum;
};
console.log(maxSum(arr, num));코드 동작 원리
- dp 배열: 위쪽 행 l부터 아래쪽 행 r까지의 열별 합을 저장하여, 2차원 문제를 1차원 최대 부분합 문제로 변환합니다.
- 카데인 알고리즘: 현재까지의 합이 음수가 되면 버리고 새로 시작함으로써, 각 행 범위에서 최대 연속 구간 합을 O(C) 만에 구합니다.
- 조건 분기: 최대값이 num 이하이면 그대로 정답 후보로 삼고, 초과하면 모든 열 구간을 검사해 num 이하인 최선의 값을 찾습니다.
이 알고리즘의 시간 복잡도는 최악의 경우 O(R² × C²)(R: 행 수, C: 열 수)이지만, 카데인 알고리즘이 대부분의 구간을 빠르게 처리해 주므로 모든 직사각형을 일일이 계산하는 완전 탐색보다 실질적으로 훨씬 빠르게 동작합니다.
실행 결과
콘솔 출력은 다음과 같습니다.
2