문제 내용
Given a
m * n matrix of ones and zeros, return how many square submatrices have all ones.Constraints:
•
1 <= arr.length <= 300•
1 <= arr[0].length <= 300•
0 <= arr[i][j] <= 1입출력 예
Example 1:
Input:[ [0,1,1,1], [1,1,1,1], [0,1,1,1] ]Output:15
Explanation:
There are 10 squares of side 1.
There are 4 squares of side 2.
There is 1 square of side 3.
Total number of squares = 10 + 4 + 1 = 15.
Example 2:
Input:[ [1,0,1], [1,1,0], [1,1,0] ]Output:7
Explanation:
There are 6 squares of side 1.
There is 1 square of side 2.
Total number of squares = 6 + 1 = 7.
이 문제는 0과 1로 이루어진 행렬에서 모든 원소가 1인 정사각형 부분 행렬의 개수를 찾는 문제입니다.
접근 1 - 브루트 포스
처음 문제를 봤을 때 가장 직관적으로 떠오르는 방법은, 각 위치를 순회하면서 그 위치에서 만들 수 있는 모든 크기의 정사각형을 확인하는 것입니다.
예를 들어 다음과 같은 3x3 행렬이 있다고 해봅시다.
예를 들어 다음과 같은 3x3 행렬이 있다고 해봅시다.
[
[1,1,1],
[1,1,1],
[1,1,1]
]
(0,0) 위치에서 시작한다면:
1.
먼저 1x1 정사각형이 가능한지 확인합니다. matrix[0][0]이 1이므로 가능하죠.
2.
그 다음 2x2 정사각형을 확인합니다. (0,0), (0,1), (1,0), (1,1) 위치가 모두 1인지 체크하면 되겠죠?
3.
마지막으로 3x3 정사각형도 확인합니다.
이런 식으로 모든 위치에서 가능한 모든 크기의 정사각형을 확인하는 거죠.
코드로 구현하면 다음과 같습니다:
코드로 구현하면 다음과 같습니다:
func countSquares(_ matrix: [[Int]]) -> Int {
let m = matrix.count
let n = matrix[0].count
var result = 0
for i in 0 ..< m {
for j in 0 ..< n where matrix[i][j] == 1 {
// 각 위치에서 가능한 모든 크기의 정사각형 확인
var size = 1
while i + size <= m, j + size <= n {
var isSquare = true
// size x size 크기의 정사각형이 모두 1인지 확인
for r in i ..< i + size {
for c in j ..< j + size where matrix[r][c] == 0 {
isSquare = false
break
}
if !isSquare { break }
}
if !isSquare { break }
result += 1
size += 1
}
}
}
return result
}
이 방식은 직관적이고 이해하기 쉽지만, 매우 비효율적입니다. 시간복잡도를 분석해보면:
1.
모든 위치를 순회:
2.
각 위치에서 최대 크기까지의 정사각형을 확인
3.
각 정사각형을 확인할 때 모든 원소를 확인:
따라서 전체 시간복잡도는 가 됩니다. 입력 크기가 커지면 감당하기 어려운 수준이죠.
접근 2 - DP
자세히 살펴보면, 이 문제에는 많은 중복 계산이 있다는 것을 알 수 있습니다.
예를 들어, 3x3 정사각형이 가능한지 확인할 때 이미 그 안에 있는 2x2 정사각형이 가능한지 여부를 알고 있다면 좋지 않을까요?
DP 배열을 다음과 같이 정의해봅시다:
dp[i][j] = (i,j) 위치에서 만들 수 있는 가장 큰 정사각형의 크기
그러면 어떤 위치 (i,j)에서 크기가 k인 정사각형이 가능하려면:
1.
위쪽으로 k-1 크기의 정사각형이 가능해야 하고 (dp[i-1][j])
2.
왼쪽으로 k-1 크기의 정사각형이 가능해야 하고 (dp[i][j-1])
3.
대각선 위로 k-1 크기의 정사각형이 가능해야 합니다 (dp[i-1][j-1])
이를 점화식으로 표현하면:
if matrix[i][j] == 1 {
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
}
완성된 코드는 다음과 같습니다:
func countSquares(_ matrix: [[Int]]) -> Int {
let m = matrix.count
let n = matrix[0].count
var dp: [[Int]] = matrix
for i in 1 ..< m {
for j in 1 ..< n where matrix[i][j] == 1 {
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
}
}
return dp.flatMap { $0 }.reduce(0, +)
}
이제 시간복잡도는 으로 크게 개선되었습니다. 각 위치를 한 번씩만 방문하면 되니까요.
그런데 여기서 한 가지 더 생각해볼 점이 있습니다. 과연 전체 dp 배열이 정말 필요할까요?
그런데 여기서 한 가지 더 생각해볼 점이 있습니다. 과연 전체 dp 배열이 정말 필요할까요?
접근 3 - DP 최적화 (1차원 배열)
dp[i][j]를 계산할 때 실제로 필요한 값들을 다시 한 번 살펴봅시다:1.
왼쪽 값 (
dp[i][j-1])2.
위쪽 값 (
dp[i-1][j])3.
왼쪽 위 대각선 값 (
dp[i-1][j-1])자세히 보면 현재 행과 이전 행의 값만 필요하다는 것을 알 수 있습니다. 그리고 실제로는 이전 행의 값도 하나의 배열로 관리할 수 있습니다.
한 행을 처리할 때:
1.
dp[j]는 이전 행의 현재 열 값 (dp[i-1][j])을 저장하고 있고2.
dp[j-1]은 현재 행의 이전 열 값 (dp[i][j-1])을 나타내며3.
prevCorner 변수로 이전 행의 이전 열 값 (
dp[i-1][j-1])을 따로 저장해두면전체 2차원 배열 없이도 필요한 모든 정보를 가질 수 있습니다!
최적화된 코드는 다음과 같습니다:
func countSquares(_ matrix: [[Int]]) -> Int {
let m = matrix.count
let n = matrix[0].count
var dp: [Int] = .init(repeating: 0, count: n)
var result = 0
var prevCorner = 0 // dp[i-1][j-1] 값을 저장
for i in 0 ..< m {
for j in 0 ..< n {
let temp = dp[j] // // 현재 dp[j]를 임시 저장
if j == 0 {
dp[j] = matrix[i][j]
} else if matrix[i][j] == 1 {
dp[j] = min(dp[j], dp[j - 1], prevCorner) + 1
} else {
dp[j] = 0
}
prevCorner = temp // // 다음 반복을 위해 저장
result += dp[j]
}
}
return result
}
이렇게 최적화하면:
1.
시간복잡도는 여전히 이지만
2.
공간복잡도는 에서 으로 크게 개선됩니다.