가장 큰 정사각형

문제 정의 - nxm의 배열에서 1로 구성된 즉 내부가 1로 가득한 정사각형중 가장 큰 정사각형의 크기를 구하여라.

입력 - n,m(1<= n,m <= 1000)

출력 - 가장 큰 정사각형의 크기를 출력하라.

Sol 1)
처음에 이 문제를 풀기 위해 단순하게 넓혀가는 방식을 생각하였다.
지금까지 가장 큰 크기를 저장해두고 그 이하의 넓이의 가로나 세로를 가지는 사각형은 모두 무시하며 지나갔다.
이런식으로 풀면 시간복잡도가O(nm)이라 3%대에서 시간초과가 난다.

Sol 2)

• O(n)으로 해결이 가능한 알고리즘이다.
• 위치를 P라하면 P(i,j)에서 대각선 위, 왼쪽, 위쪽을 탐색한다.
• 왼쪽 대각선 위, 왼쪽, 위쪽이 모두 양수를 가지는지 확인한다.
• 셋 다 양수라면 가장 작은 수에 +1을 하여 P(i,j)에 넣어준다.
• 마지막에 P(0,0)부터 P(n,m)까지 탐색하여 가장 큰수의 제곱을 출력

위의 사진에서는 4가 가장큰 수이므로 16을 출력하게 된다.