
가장 큰 정사각형
·
BackEnd/알고리즘 공부
https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 문제 설명 2차원 배열을 알려 주면 칸에 숫자가 1인 제일큰 정사각형의 넓이를 찾으면 된다. 문제에 대한 이이디어 이런 문제들은 점화식을 잘 찾아서 사용해야 한다. 그래서 더 어려운 것 같다. 정사각형의 넓이를 찾아라를 쉽게 말하면 정사각형이 될 수 있는 한 변의 최대 길이를 찾아라 라고 할 수 있다. 어떻게 정사각형의 한 변의 길이를 찾을 수 있을까? 정사각형의 조건은 가로 세로의 길이가 같고 또 모든 인접한 면이 1이어야 한다. 지금 자신이 1이라면 왼쪽 대각선 ..