파이썬으로 2D 행렬에서 k×k 부분 행렬의 최솟값 구하기

문제 개요

2차원 행렬과 정수 k가 주어졌을 때, 행렬 안에 존재하는 모든 k × k 부분 행렬(sub-matrix) 각각의 최솟값들을 모아 새로운 행렬로 반환하는 것이 이번 문제의 목표입니다.

예를 들어, 다음과 같은 3×3 행렬이 입력으로 주어진다고 가정해 보겠습니다.

여기서 k = 2라고 하면, 출력은 [[3, 5], [3, 3]]이 됩니다.

부분 행렬별 최솟값 확인

왼쪽 위 부분 행렬의 최솟값은 3입니다.

3 5
8 6

오른쪽 위 부분 행렬의 최솟값은 5입니다.

5 6
6 5

왼쪽 아래 부분 행렬의 최솟값은 3입니다.

8 6
4 3

오른쪽 아래 부분 행렬의 최솟값은 3입니다.

6 5
3 12

해결 접근 방법: 슬라이딩 윈도우 + 덱(Deque)

모든 부분 행렬을 일일이 탐색하면 비효율적이므로, 슬라이딩 윈도우 최솟값(sliding window minimum) 기법을 활용합니다. 핵심 아이디어는 다음과 같습니다.

• 1단계 — 행(row) 방향 처리: 각 행에 대해 길이가 k인 윈도우 내 최솟값을 덱(deque)을 이용해 계산하고, 그 결과로 행렬을 갱신합니다.

• 2단계 — 열(column) 방향 처리: 갱신된 행렬의 각 열에 대해 동일한 슬라이딩 윈도우 최솟값 연산을 수행합니다.

• 3단계 — 결과 추출: 두 방향의 연산이 끝나면, 위치 (i + k − 1, j + k − 1)에 있는 값이 곧 (i, j)번째 k × k 부분 행렬의 최솟값이므로 해당 영역만 잘라내어 반환합니다.

덱에는 인덱스를 저장하며, 앞쪽에는 현재 윈도우 범위를 벗어난 인덱스를 제거하고, 뒤쪽에서는 새로 들어오는 값보다 큰 값들의 인덱스를 제거함으로써 항상 윈도우의 최솟값이 덱 맨 앞에 오도록 유지합니다. 이렇게 하면 전체 시간 복잡도를 O(n × m)으로 유지할 수 있습니다.

파이썬 구현 예제

다음 구현을 통해 더 자세히 이해해 보겠습니다.

import collections
class Solution:
   def solve(self, matrix, k):
      for r, row in enumerate(matrix):
         q = collections.deque()
         nrow = []
         for i in range(len(row)):
            if q and q[0] == i - k:
               q.popleft()
            while q and row[q[-1]] > row[i]:
               q.pop()
            q.append(i)
            nrow.append(row[q[0]])
         matrix[r] = nrow
      for j in range(len(matrix[0])):
         q = collections.deque()
         ncol = []
         for i in range(len(matrix)):
            if q and q[0] == i - k:
               q.popleft()
            while q and matrix[q[-1]][j] > matrix[i][j]:
               q.pop()
            q.append(i)
            ncol.append(matrix[q[0]][j])
         for i in range(len(matrix)):
            matrix[i][j] = ncol[i]
      ret = [[0] * (len(matrix[0]) - k + 1) for _ in range(len(matrix) - k + 1)]
      for i in range(len(ret)):
         for j in range(len(ret[0])):
            ret[i][j] = matrix[i + k - 1][j + k - 1]
         return ret
ob = Solution()
print(ob.solve(matrix = [
   [3, 5, 6],
   [8, 6, 5],
   [4, 3, 12]
], k = 2))

입력

[[3, 5, 6],[8, 6, 5],[4, 3, 12]], 2

출력

[[3, 5], [3, 3]]

마무리

이 알고리즘은 덱을 활용한 슬라이딩 윈도우 최솟값 기법을 행과 열 방향으로 각각 한 번씩 적용하는 방식입니다. 브루트 포스 방식(O(n × m × k²))과 달리 선형 시간에 해결할 수 있어, 행렬의 크기가 커질 때 특히 효율적입니다. 이미지 처리의 최소 필터(min filter) 연산 등 실제 응용 분야에서도 널리 쓰이는 패턴이니 꼭 익혀두시길 권장합니다.