문제 설명
주어진 이진 행렬에서 1로 구성된 가장 큰 정사각형을 찾는 문제입니다. 행렬의 각 요소는 0 또는 1이며, 1은 정사각형의 일부로 포함될 수 있습니다.
정사각형의 크기를 결정하는 것은 각 1의 가장자리 값을 기반으로 하며, 따라서 문제를 해결하기 위해 다이나믹 프로그래밍(Dynamic Programming) 접근 방식을 사용할 것입니다.
입력 형식
행렬의 크기 n x m이 주어질 때, 다음과 같은 형식으로 입력됩니다.
[
['1', '0', '1', '0', '0'],
['1', '0', '1', '1', '1'],
['1', '1', '1', '1', '1'],
['1', '0', '0', '1', '0']
]
출력 형식
가장 큰 정사각형의 넓이를 정수로 반환합니다.
예제 입력 및 출력
입력:
[
['1', '0', '1', '0', '0'],
['1', '0', '1', '1', '1'],
['1', '1', '1', '1', '1'],
['1', '0', '0', '1', '0']
]
출력: 4
문제 풀이 과정
1. 문제 이해 및 분석
이 문제는 이진 행렬에서 ‘1’으로 이루어진 최대 정사각형을 찾아야 합니다.
이를 위해 각 요소에 대해 가능한 정사각형의 크기를 추적해야 합니다.
행렬에서 각 요소의 값은 정사각형의 오른쪽 아래 모서리를 기준으로 다음과 같은 규칙을 적용하여 결정됩니다.
만약 (i, j) 위치의 요소가 ‘1’이라면, 해당 위치를 오른쪽 아래 모서리로 하는 정사각형의 크기는
왼쪽 (i, j-1), 위쪽 (i-1, j), 그리고 왼쪽 위 대각선 (i-1, j-1) 위치의 값 중 가장 작은 값 + 1이 됩니다.
이를 통해 현 위치에 포함되는 ‘1’들을 분석하여 최대 정사각형의 넓이를 찾을 수 있습니다.
2. 알고리즘 설계
문제를 해결하기 위해 다음과 같은 단계로 다이나믹 프로그래밍(DP)을 적용합니다.
- 입력으로 주어진 이진 행렬의 크기를 확인하고 DP 배열을 생성합니다.
- 이진 행렬의 각 요소를 확인하며 1을 만날 때마다 DP 배열을 업데이트합니다.
- DP 배열의 최대 값을 찾아 그 제곱을 반환하여 최대 정사각형의 넓이를 계산합니다.
3. 코드 구현
위의 알고리즘 설계를 바탕으로 C++로 코드를 구현해보겠습니다.
아래는 최종 구현 코드입니다.
#include
#include
#include
using namespace std;
int maximalSquare(vector>& matrix) {
if (matrix.empty()) return 0;
int maxSide = 0;
int rows = matrix.size(), cols = matrix[0].size();
vector> dp(rows + 1, vector(cols + 1, 0));
for (int i = 1; i <= rows; ++i) {
for (int j = 1; j <= cols; ++j) {
if (matrix[i - 1][j - 1] == '1') {
dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
maxSide = max(maxSide, dp[i][j]);
}
}
}
return maxSide * maxSide; // return area
}
int main() {
vector> matrix = {
{'1', '0', '1', '0', '0'},
{'1', '0', '1', '1', '1'},
{'1', '1', '1', '1', '1'},
{'1', '0', '0', '1', '0'}
};
cout << "가장 큰 정사각형의 넓이는: " << maximalSquare(matrix) << endl;
return 0;
}
4. 코드 분석
이 코드는 0으로 초기화된 DP 배열을 생성하고, 입력 행렬을 순회하면서
각 위치에서 최대 정사각형의 크기를 업데이트합니다. 배열의 크기 (rows + 1) x (cols + 1)을 사용하는 이유는
DP 배열의 경계 조건을 쉽게 처리하기 위함입니다.
가장 큰 변의 길이를 저장하는 maxSide 변수를 통해 최종적으로 정사각형의 면적을 계산합니다.
5. 성능 분석
이 알고리즘의 시간 복잡도는 O(n * m)이며, 공간 복잡도 또한 O(n * m)입니다.
행렬의 크기 n x m에 비례하여 증가하는 성능을 가지므로, 이 문제는 대규모의 행렬에 대해서도 효율적으로 처리할 수 있습니다.
결론
이 글에서는 C++을 이용하여 이진 행렬에서 가장 큰 정사각형의 넓이를 찾는 알고리즘 문제를 해결하는 방법을 다루었습니다.
다이나믹 프로그래밍을 활용한 접근 방식은 문제를 분해하고 최적의 해를 찾는 데 매우 효과적입니다.
본 강좌를 통해 C++의 자료구조와 알고리즘을 더 깊이 이해하고 실습할 수 있는 기회가 되었기를 바랍니다.