Dynamic Programming - 최대 공백 정사각형, 최대 공백 직사각형

최대 공백 정사각형 - O(n²)

• n x n 크기의 흑백 이미지에서 검은 점을 포함하지 않는 가장 큰 빈 정사각형 찾기.

오른쪽 아래 구석인 x, y 위치에서 만들 수 있는(x,y 를 포함하는)
가장 큰 정사각형의 크기가 LES(x, y) 에 저장됨.

1. (x, y) == 1 이라면 (그 자리에 검은점이 존재하면)
LES(x, y) = 0

2. 1행 or 1열의 경우 검은점 자리를 제외한 나머지의
LES(x, y) = 1

3. (x,y) == 0 이라면
LES(x, y) = Min(LES(x-1, y-1), LES(x, y-1), LES(x-1, y)) + 1

---

최대 공백 직사각형 - O(n²)

• 넓이가 제일 큰 빈 직사각형 찾기.
• 스택 문제로부터 아이디어

1. 입력을 높이 입력으로 변환
⇒ 높이로의 변환을 쉽게 하기 위하여 DP 처럼 맨 윗줄 부터 계산 → O(n²)
⇒ 스택을 이용하여 안쪽으로 얼만큼의 직사각형이 가능한지 계산?

2. 파란색을 윗변으로 하는 직사각형중 넓이가 가장 큰것이 답.

어려워요..