[백준] 1915번, 가장 큰 정사각형 (JavaScript)

Algorithm

📌 문제 정보 : 가장 큰 정사각형

• 문제 분류 : 다이나믹 프로그래밍 (DP)
• 문제 출처 : 백준 골드 4, 가장 큰 정사각형

✅ 접근 과정

문제의 요구조건을 보았을 때, 최대 1000 * 1000 크기의 배열에서 1로 이루어진 가장 큰 정사각형을 찾아야 한다.
단순히 모든 인덱스를 순회 한다면 1,000,000 번이 걸리고 여기서 최대 정사각형의 크기를 찾기 위해서는 현재 인덱스가 (i, j)일 때, 최대 i 곱하기 j의 연산을 추가로 해야 하므로 대략 1000 ** 4의 시간이 걸려서 시간 초과가 발생한다.

이를 해결하기 위해 DP를 사용하여 [N][M]부터 [0][0]까지 인접한 인덱스 (오른쪽, 아래쪽, 오른쪽 아래 대각선)을 확인하며 1로 이루어진 정사각형의 크기를 빠르게 구하기로 했다.

유용했던 반례 : https://www.acmicpc.net/board/view/48661

✨ 풀이 코드

• 다른 분들의 풀이를 살펴보니 이 풀이처럼 인덱스를 감소시키는 방법이 아닌 (0, 0)부터 (N - 1, M - 1)까지 인덱스를 증가시키며 찾는 방법이 더 직관적인 풀이인 거 같다. (풀이 과정은 동일하다.)

🚩 마치며

어려워 보였지만 DP를 떠올리니 금방 풀 수 있었다.