C++로 주어진 합을 갖는 부분 행렬 찾기

이 문제에서는 N×N 크기의 2차원 행렬과 두 개의 변수 sum(합계), size(크기)가 주어집니다. 우리의 과제는 주어진 합을 갖는 부분 행렬(sub-matrix)을 찾는 것입니다.

즉, 요소들의 합이 sum과 같은 size×size 크기의 부분 행렬이 존재하는지 확인해야 합니다.

문제 이해를 위한 예시

입력 : mat[][] = {
    {1, 5, 7, 9}
    {2, 4, 6, 8}
    {1, 2, 5, 6}
    {3, 6, 9, 3}
}
sum = 22
size = 2
출력 : YES

설명 −

합이 22인 크기 2의 부분 행렬은 다음과 같습니다.
{5, 7}
{4, 6}

해결 접근 방법

가장 단순한 해결 방법은 가능한 모든 size×size 크기의 부분 행렬을 만들어 각각의 합을 구하고, 그 값이 주어진 sum과 일치하는지 비교하는 것입니다. 일치하면 해당 부분 행렬이 존재한다고 반환하면 됩니다.

하지만 더 효율적인 방법은 동적 계획법(Dynamic Programming) 개념을 활용하는 것입니다. 이 방식에서는 누적 합을 저장하는 DP 배열을 생성합니다. 즉, DP[i][j]에는 행 인덱스 0부터 i까지, 열 인덱스 0부터 j까지의 모든 요소의 합이 저장됩니다.

이 DP 배열을 사용하면 임의의 시작 인덱스와 끝 인덱스 사이의 부분 행렬 합을 다음 공식으로 빠르게 계산할 수 있습니다.

$$\mathrm{sum((i_s,j_s)to(i_e,j_e))\:=\:DP[i_e][j_e]\:+\:DP[i_s-1][j_s-1]\:-\:DP[i_s-1][j_e]\:-\:DP[i_e][j_s-1]}$$

알고리즘

1단계 − 크기가 (n+1)×(n+1)인 DP 행렬을 생성합니다.

2단계 − 행렬의 각 요소에 대해 현재 인덱스까지의 누적 합을 DP 배열에 저장합니다.

3단계 − 0부터 n까지의 모든 인덱스에 대해 위 공식을 사용하여 size×size 크기의 부분 행렬의 합을 계산하고 currSum에 저장합니다.

4단계 − currSum == sum이라면 true를 반환합니다.

5단계 − 끝까지 찾지 못했다면 false를 반환합니다.

구현 예제

다음 프로그램은 위에서 설명한 솔루션의 동작을 보여줍니다.

#include <iostream>
using namespace std;
#define N 4
bool findSubMatWithSum(int size, int sum, int mat[N][N]){
    int DP[N + 1][N + 1];
    for (int i = 0; i <= N; i++)
    for (int j = 0; j <= N; j++)
    DP[i][j] = 0;
    for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
    DP[i + 1][j + 1] = DP[i + 1][j] + DP[i][j + 1] - DP[i][j] + mat[i][j];
    int currSum = 0;
    for (int i = 0; i <= N - size; i++)
    for (int j = 0; j <= N - size; j++) {
       currSum = DP[i][j] + DP[(i + size)][(j + size)] - DP[(i + size)][j] - DP[i][(j + size)];
       if (currSum == sum)
       return true;
    }
    return false;
}
int main(){
    int mat[N][N] = { { 1, 5, 7, 9 },
    { 2, 4, 6, 8 },
    { 1, 2, 5, 6 },
    { 3, 6, 9, 3 } };
    int size = 2;
    int sum = 22;
    if (findSubMatWithSum(size, sum, mat))
       cout<<"주어진 크기와 합을 갖는 부분 행렬이 존재합니다!"<<endl;
    else
       cout<<"주어진 크기와 합을 갖는 부분 행렬이 존재하지 않습니다!"<<endl;
}

출력 결과

주어진 크기와 합을 갖는 부분 행렬이 존재합니다!

복잡도 분석

DP 배열을 활용하면 각 부분 행렬의 합을 O(1) 시간에 구할 수 있으므로, 전체 시간 복잡도는 O(N²)이 됩니다. 반면 모든 부분 행렬을 직접 탐색하는 단순한 방식은 O(N² × size²)의 시간이 걸리므로, 누적 합 기반 접근이 훨씬 효율적입니다. 추가로 사용되는 DP 배열 때문에 공간 복잡도는 O(N²)입니다.