코딩 테스트에서 자주 등장하는 문제 중 하나는 이차원 배열에서 가장 큰 정사각형을 찾는 문제입니다. 이 문제는 다음과 같은 방식으로 정의할 수 있습니다.
문제 정의
주어진 이진 행렬 (0과 1로 구성된 2차원 배열)에서 1로 구성된 가장 큰 정사각형의 넓이를 구하시오.
예를 들어, 다음과 같은 행렬이 있다고 가정합시다.
[
[1, 0, 1, 0, 0],
[1, 0, 1, 1, 1],
[1, 1, 1, 1, 1],
[1, 0, 0, 1, 0]
]
위의 행렬에서 가장 큰 정사각형은 (1, 1)부터 (3, 3)까지의 영역으로, 크기는 9입니다.
문제 접근과 풀이 과정
이 문제를 해결하기 위해서는 동적 프로그래밍(Dynamic Programming) 방법을 사용할 수 있습니다. 이 방법론은 문제를 더 작은 하위 문제로 나누어 해결하고, 그 결과를 사용하여 최종 결과를 도출합니다.
동적 프로그래밍을 사용한 접근
1. 우리는 먼저 주어진 행렬의 크기를 가져오고, 동적 프로그래밍을 위한 2차원 배열 dp를 정의합니다. 이 dp 배열의 각 요소는 특정 위치에서의 가장 큰 정사각형의 한 변의 길이를 나타냅니다.
2. 초기화: dp 배열의 각 요소를 0으로 초기화합니다. 다만, 주어진 행렬의 첫 번째 행과 첫 번째 열은 주어진 행렬이 1인 위치에 대해서만 1로 설정합니다.
3. dp 배열을 채워나가는 방식: 이진 행렬의 각각의 요소를 살펴보면서, 특정 위치 (i, j)의 값이 1인 경우, dp[i][j] 값은 dp[i-1][j], dp[i][j-1], dp[i-1][j-1] 중 최소값 + 1로 설정합니다. 이는 가장 큰 정사각형의 변을 계산하는 방법입니다.
4. 결과: dp 배열에서 가장 큰 값을 찾아야 하며 이 값의 제곱이 우리가 구하고자 하는 정사각형의 넓이가 됩니다.
동적 프로그래밍 구현
이제 위의 방법을 토대로 파이썬 코드를 작성해 보겠습니다.
def maximalSquare(matrix):
if not matrix:
return 0
max_square_len = 0
rows = len(matrix)
cols = len(matrix[0])
dp = [[0] * cols for _ in range(rows)]
for i in range(rows):
for j in range(cols):
if matrix[i][j] == '1':
if i == 0 or j == 0:
dp[i][j] = 1
else:
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
max_square_len = max(max_square_len, dp[i][j])
return max_square_len * max_square_len
코드 설명
코드의 첫 번째 줄에서는 주어진 행렬이 비어있지 않은지를 체크합니다. 비어있다면 결과는 0이 됩니다.
그 다음, 행렬의 행과 열의 크기를 가져오고, dp 배열을 생성합니다. 이 배열은 주어진 이진 행렬과 동일한 크기를 가지며 각 요소는 0으로 초기화됩니다.
포문을 통해 각 요소를 반복하며, 현재 요소가 1인 경우에만 처리를 진행합니다. 이 때, 각 요소를 처리하기 위해서는 위에서 언급한 관계를 사용하여 dp 배열을 채워 나갑니다. 여기서 가장 큰 정사각형의 변의 길이를 항상 추적하여 업데이트합니다.
마지막에는 가장 큰 정사각형의 넓이를 반환합니다.
복잡도 분석
위의 알고리즘은 O(n * m)의 시간 복잡도를 가집니다. 여기서 n은 행렬의 행의 수, m은 열의 수입니다. 공간 복잡도는 O(n * m)으로, 이는 dp 배열을 저장하기 위한 공간입니다.
예시와 함께 하기
이제 이 함수를 사용하여 주어진 행렬에서 가장 큰 정사각형을 찾아보겠습니다.
matrix = [
["1", "0", "1", "0", "0"],
["1", "0", "1", "1", "1"],
["1", "1", "1", "1", "1"],
["1", "0", "0", "1", "0"]
]
print(maximalSquare(matrix)) # 9
결론
이 문제는 코딩 테스트에서 자주 등장하는 문제 유형 중 하나입니다. 연습을 통해 이 문제를 잘 이해하고 해결할 수 있다면, 유사한 다른 문제들을 푸는 데에도 큰 도움이 될 것입니다. 더 나아가, 동적 프로그래밍의 원리를 이해하고 적용할 수 있는 능력은 여러 알고리즘 문제 해결에 유용하게 작용할 것입니다.
추가적으로, 이진 행렬을 더 복잡한 형태로 확장하는 복잡한 변형 문제를 다룰 수도 있습니다. 예를 들어, 주어진 행렬에서 0과 1의 구조가 달라지는 경우, 또는 주어진 조건을 만족하는 다른 형태의 정사각형이나 직사각형을 찾아야 할 경우 등 다양한 문제 유형이 존재합니다.
더 나아가기
더 많은 알고리즘 문제를 풀어보고, 시간 복잡도, 공간 복잡도 등을 고려하여 최적화하는 연습을 계속하세요. 이 과정에서 자주 사용하는 자료구조와 알고리즘을 깊이 있게 학습하는 것도 매우 중요합니다. 또한, 다양한 문제를 접하다 보면 자연스럽게 문제 해결 능력이 향상될 것입니다.
앞으로도 많은 알고리즘 강좌를 통해 여러분의 코딩 실력을 함께 키워나가길 바랍니다!