[BOJ 1915] 가장 큰 정사각형(C++)
가장 큰 정사각형(Gold4) 문제 전체 문제 보기 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 접근법 처음 문제에 접근할 때 완전 탐색이 가능한지 먼저 확인해보는 것이 중요합니다. 임의의 위치 \((r, c)\)에서 만들 수 있는 정사각형의 최대 크기를 탐색해보기 위해서는 \(O(n^4)\)의 계산량이 필요합니다. 아쉽게도 이번 문제에서는 \(n\)의 크기가 최대 \(1,000\)이기 때문에 완전 탐색으로는 풀 수 없는 문제입니다. 이번 문제는 동적계획법을 활용한 최적화가 필요합니다. 동적 계획법으로 풀기 위해서 점화식을 다음과 같이 세울 수 있습니다. // dp[r][c]..
