[백준] 1915 가장 큰 정사각형

참고: https://www.acmicpc.net/problem/1915

1915번: 가장 큰 정사각형

---

n * m 크기의 배열에서 1로된 가장 큰 정사각형의 크기를 구하는 문제입니다. DP를 사용하여 해결할 수 있습니다.

이미 DP로 분류되어있는 것을 알았기 때문에, 저는 바로 DP로 접근했습니다. 하지만 문제 유형에 대한 단서가 주어지지 않았다면 해결 방법을 찾는데 시간을 좀 더 많이 소비 했을 것 같습니다.

 

다이나믹 프로그래밍 알고리즘은 문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해 뒀다가 나중에 큰 문제의 결과와 합하여 푸는 알고리즘입니다. 이러한 문제를 최적 부분 구조를 가진 문제라고도 합니다.

 

최적 부분 구조를 가진 문제를 풀 수 있는 방법으로는 그리디, 분할 정복, DP가 있습니다. 만약 최적 부분 구조 문제를 푼다면 이 세가지 알고리즘을 후보로 두고 유형을 파악해야합니다. 아래 표에 세 알고리즘으로 풀 수 있는 문제들의 차이점을 정리해두겠습니다.

 

알고리즘	풀이 가능한 문제들의 특징	풀이 가능한 문제 및 알고리즘
다이나믹 프로그래밍	- 최적 부분 구조 - 중복된 하위 문제들	- 0 - 1 배낭 - 피보나치 수열 - 다익스트라 알고리즘
그리디 알고리즘	- 최적 부분 구조 - 탐욕 선택 속성	- 분할 가능 배낭 문제 - 다익스트라 알고리즘
분할 정복	- 최적 부분 구조	- 병합 정렬 - 퀵 정렬

최적 부분 구조는 부분 문제에 대한 최적 해결 방법을 합하여 전체 문제를 최적으로 해결할 수 있는 문제를 말합니다.

탐욕 선택 속성은 앞의 선택이 이후 선택에 영향을 주지 않는 것을 말합니다. 다시말해, 선택을 다시 고려하지 않는다는 것입니다.

중복된 하위 문제들은 피보나치 수열과 동일한 문제들이 반복되는 구조의 문제를 말합니다.

 

 

이제 문제를 풀어보겠습니다.

 

1	1
1	1

2 * 2 배열이 있습니다. 이중 for문을 사용한다고 가정했을 때, 위 배열에서 가장 큰 정사각형의 크기를 판단할 수 있는 위치는 2행 2열입니다. 1행 1열, 1행 2열, 2행 1열이 모두 1인지 검사하고 자신이 1이라면 정사각형의 크기를 구할 수 있기 때문입니다.  

1	1
1	2

 

 

 

배열을 더 키워서 3 * 3 크기의 배열을 예로 들어보겠습니다.

1	1	1
1	1	1
1	1	1

해당 배열을 위에서 말씀드린 알고리즘으로 그 값을 구한다면 아래와 같을 것 입니다.

 

1	1	1
1	2	?
1	?	?

2행 2열의 값은 단번에 2라는 것을 알 수 있습니다. 하지만 '?'의 값은 어떻게 될까요?

직관적으로 2행 3열과 3행 2열은 2, 3행 3열은 3이 된다는 것을 알 수 있습니다. 하지만 정확하게 판단 근거를 세워야 합니다. 위 배열을 약간 수정해보겠습니다.

 

1	1	0
1	2	1
1	2	?

1행 3열의 1이 0으로 바뀌었습니다. 이제 2행 3열은 더이상 2가 아닌 1이 될 것입니다. 그렇다면 직관적으로 3행 3열의 값은 2라는 것을 알 수 있습니다. 1행 3열이 0이 되어 더이상 정사각형이 아니기 때문입니다.

 

이제 '?'의 값들이 어떻게 정해지는 지 알 수 있을 것입니다. 만약 검사한 3개의 값들이 모두 2라면 3행 3열의 값을 제외한 모든 값들이 1이라는 것이고, 단 하나라도 1이면 그 값들 중 최소한 하나는 0이 포함되어있다는 의미입니다.

 

따라서 검사한 세 개의 값들 중 최소 값을 찾아 1을 더한다면 현재 구하고자는 위치의 값을 구할 수 있을 것입니다.

 

Python

Java