[Leetcode 85번 문제] Maximal Rectangle

문제 요약

0과 1로 이루어진 2차원 매트릭스가 주어진다. 이 안에서 직사각형의 성질을 만족하는 가장 큰 넓이를 구하여라

입력

2차원 배열이 주어지고, 행과 열의 최대 크기는 200씩



이 문제를 푸는 정공법은 스택이라고 할 수 있을 것 같다. 그런데 난 이 문제를 처음 봤을때 때 DP를 떠올렸다. 정확히 왜 그랬냐 하면
DP문제는 겹치는 부분이 존재한다. 피보나치 수열 같이 a(n) = a(n - 1) + a(n - 2) 가 대표적 이 문제에서도 역시 그런 겹치는게 보였기 때문이다.

동적프로그래밍은 굉장히 많은경우에 문제의 답이 되는 경우가 많다. 많은 경우에 백트래킹보다 빠르고 경우의 수를 탐색할때 최적일 때가 많아서 그렇다.

하지만 그만큼 DP도 한가지 방법만 있는게 아니라 여러가지 접근이 가능하기에 어떻게 바라봐야 확실하게 문제를 풀 수 있을까라는 고민이 많다. 그리고 이문제를 풀면서
약간 그 해답중 한가지 예시를 볼 수 있었던 것같다.

과정

일단 DP답게 ’해당 칸‘에 영향을 주는 모든 경우의 수를 찾거나. 반대로 해당 칸이 영향을 줄 수 있는 모든 칸들을 찾으려 했다.

일단 DP의 방향을 직렬화 하기위해서 아래, 오른쪽만 가정하는 상황으로 만든다. 점 a가 1일때만 계산을 해주면되고
오른쪽에서 가장 길게 연속적으로 1을 만들수 있는길이와, 아래쪽으로 가장 길게 1을 만든수 있는 길이를 얻어낸다.
길이 배열을 만들어서 본인이 1일경우 바로 아래칸의 (아래 길이 + 1) 아닐경우 0을 저장하고 오른쪽의 경우도 마찬가지로 하면 DP적으로 값을 얻을 수 있을 것 같았다.

그렇게 가로와 세로의 길이를 찾아놓고 넓이는 자기 아래 대각선칸에서 찾으려했다. 이러면 모든 경우의 수를 다 커버할 수 있는 DP식이 아닐까? 하고 생각했다 이방식 대로 하면
(R, C)의 배열이 총200 * 200개에 전체 테이블역시 200 * 200이기 떄문에
O(n ** 4), 총 1억 6천만번의 연산으로 시간이 초과할 것 같다는 생각이 들었다.
더 나은 DP가 있을거같다는 생각이 들었지만 결국 찾지못했고. 아까말한 스택으로 문제를 풀었다. 문제를 풀고나서 다른사람의 코드를 보고나서 이문제를 DP로도 풀 수 있다는걸 알았다.

풀이방법

1. 공통된 부분을 찾는다
나는 관습적으로 매트릭스의 한 칸을 DP 대상으로 삼았는데 사각형의 성질을 생성하면 이 문제는 가로나 세로중 하나를 고정할 수 있었다. 한 행의 부분 변에 대해서 높이를 파악하면 한 행의 모든 넓이를 알 수있다.
단순 이것만 한다면 조삼모사이다. 한 행에서 가능한 모든 변의 종류도 n ** 2이고 높이를 구하면 최대 O(n ** 3) 이기 때문이다. 모든행을 구하는데 시간은 같다

그러면 더 나아가서 여기서 시간을 줄이기 위해서는 직렬화해서 DP를 써야한다

한 변을 직렬화 하는법
변이 점의 집합이라는걸 생각해보자. 이런 생각을 해야한다. 한 변을 한 점의 왼쪽(또는 오른쪽)에 있는 점들이라고 할 수 있을까? 사실 그럴수가 없다. 근데 왜?

각 행의 생김새가 이렇게 생겼는데 여기서 사각형의 넓이는
자신의 높이 * (자신의 높이보다 같거나 높은 왼쪽 칸의 개수 + 자신의 높이보다 같거나 높은 오른쪽 칸의 개수 + 1) 이 된다
여기서 DP를 위해 왼쪽 칸의 개수만 고려하면 파란색의 경우를 캐치하지 못한다.

느낀점

난 DP에서 항상 이전의 값이 이후에 영향을 준다고 생각하고 문제를 풀었다. 그런데 이번 문제처럼 여러가지 방향에서 영향을 주는 값을 동시애 고려해야 할 수도 있다는걸 알게되니 더 많은 생각을 한 것 같다.