이번 문제에서 가장 큰 정사각형을 구하기 위해서 모든 경우의 수를 하나씩 탐색한다면, 이 문제를 풀 수가 없다. 최대 크기의 사각형에서 모든 경우의 수를 다 구하기 위해서는 방법이 무지막지하게 많아진다. 그렇다면 다른 방법은 무엇이 있을까? 답은 다이나믹 프로그래밍을 이용하는 것이다. 다이나믹 프로그래밍을 이용하여 시간복잡도 O(NM) 으로 풀이가 가능하다. 예시를 보면서 풀이 방법에 대하여 천천히 알아보자. 예시로 보여준 그림이 있다. 탐색 순서는 위에서 아래로, 좌측에서 우측으로 이동하며 탐색한다. dp 배열은 입력으로 들어온 배열과 크기가 같다. 첫번째 붉은색 상자를 보자. 상자 안에는 0이 2개, 1이 2개 있다. 해당 칸은 정사각형을 이룰 수 있는가? 답은 이룰수 없다. 이렇게 된 결과를 dp ..
