백준 알고리즘 풀이 1915번 - 가장 큰 정사각형

https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net - 다이나믹 프로그래밍 - 알고리즘 - 1. 전체 맵의 오른쪽 아래를 기준으로 정사각형의 왼쪽 위라고 가정한다. 2. counts[][] 배열을 만들어서 그 지점을 좌측 상단으로 하는 가장 큰 정사각형이라고 정의한다. 3. counts[a][b] = min(counts[a+1][b],counts[a][b+1],counts[a+1][b+1])+1 -시간 복잡도- 맵의 총크기 : O(n) * O(n) 각 경우당 4번씩 탐색. 따라서 총 시간 복잡도 = 4 * O(n) *..

2019.10.15