문제 링크: https://leetcode.com/problems/maximal-square/description/
1로만 채워진 가장 큰 정사각형을 구하는 문제이다.
Approach 1: Brute Force
가장 단순한 방법은 matrix 의 모든 cell 을 순회하며, 각 cell 이 형성할 수 있는 가장 큰 정사각형을 구하는 방식이다.
방법은 아래와 같다.
1. matrix 를 순회하며, 각 cell 을 left uppermost 로 하는 가장 큰 정사각형을 구한다.
2. cell 이 1이면 다음 계산을 수행한다.
- 일시적으로 row, col 을 1씩 증가 시켜 해당 row 와 col 에 속한 cell 들이 전부 1인지 확인한다.
- 전부 1이면, 대각선 아래방향으로 이동한다.
- 0이 하나라도 있다면, 검사를 멈추고 다음 cell 로 이동한다.
모든 cell 을 순회하며, 각 cell 마다 최대 정사각형을 검사하므로 Time Complexity 는 O((mn)^2) 이다.
추가 공간은 들지 않았으므로 Space Complexity 는 O(1) 이다.
from typing import List
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
ROWS, COLS = len(matrix), len(matrix[0])
res = 0
# 순회하며, 각 cell 을 left uppermost 로 하는 가장 큰 정사각형을 구한다.
for i in range(ROWS):
for j in range(COLS):
if matrix[i][j] == "1":
sideLen = 1 # 정사각형 한 변의 길이를 1로 세팅
while i + sideLen < ROWS and j + sideLen < COLS:
flag = True
# 일시적으로 row, col 을 증가시켜서 해당 row 와 col 에 속한 cell 들이 전부 1 인지 검사
for r in range(i, i + sideLen + 1):
if matrix[r][j + sideLen] != "1":
flag = False
break
for c in range(j, j + sideLen + 1):
if matrix[i + sideLen][c] != "1":
flag = False
break
# 0이 하나라도 있으면, 검사를 멈춘다.
if not flag:
break
# 전부 1이면, 대각선 아래 방향으로 이동한다.
sideLen += 1
res = max(res, sideLen)
return res * res
Approach 2: Dynamic Programming
이 문제에 주어진 것처럼 "longest/shortest/largest/smallest/maximal" 같은 키워드가 있으면,
최적 부분 구조의 특성을 찾아 DP 로 효율적으로 해결할 수 있는 케이스가 많다.
최적 부분 구조 (optimal-substructure) 란?
큰 문제를 작은 문제로 나누고, 이 작은 문제들을 해결하여 그 해답을 조합해서 전체 문제의 최적 값을 찾을 수 있는 구조
최적 부분 구조의 특성을 이 문제에도 적용할 수 있다.
아래 그림에서, 노란색 동그라미 cell 을 bottom right 으로 하는 정사각형의 최대값을 구하려면
파란색 동그라미 cell 을 bottom right 으로 하는 정사각형의 최대값들을 이용하면 된다.
이를 적용하여 dp 식을 세워보면 다음과 같다.
dp(i, j)=min(dp(i−1, j), dp(i−1, j−1), dp(i, j−1))+1
from typing import List
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
ROWS, COLS = len(matrix), len(matrix[0])
dp = [[0] * (COLS + 1) for _ in range(ROWS + 1)]
res = 0
for i in range(1, ROWS + 1):
for j in range(1, COLS + 1):
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
res = max(res, dp[i][j])
return res * res
matrix 순회를 한 번만 했으므로, Time Complexity 는 O(mn) 이다.
matrix 크기와 똑같은 dp 배열 하나를 생성했으므로 Space Complexity 는 O(mn) 이다.
Approach 3: Dynamic Programming (with Space Optimization)
똑같은 DP 풀이지만 약간의 공간 최적화를 해서 Space Complexity 를 줄인 코드이다.
사실, 노란색 동그라미 값을 구하기 위해서 모든 dp 값을 배열로 들고 있을 필요가 없다.
아래 그림에서 표시한 이전 row 에 대한 dp 정보만 알고 있으면 되는 것이 공간 최적화의 핵심이다.
from typing import List
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
ROWS, COLS = len(matrix), len(matrix[0])
res = 0
prev = [0] * (COLS + 1)
for i in range(1, ROWS + 1):
tmp = [0] * (COLS + 1)
for j in range(1, COLS + 1):
if matrix[i - 1][j - 1] == "1":
tmp[j] = min(tmp[j - 1], prev[j], prev[j - 1]) + 1
res = max(res, tmp[j])
prev = tmp
return res * res
이전 row 에 대한 dp 정보를 담고 있기 위해 prev 배열을 선언했으므로, Space Complexity 는 O(n) 이다.
(Approach 2 풀이보다 개선된 걸 볼 수 있다)