[프로그래머스] 가장 큰 정사각형 찾기

문제 링크

코딩테스트 연습 - 가장 큰 정사각형 찾기

 

풀이

가로의 길이가 1이거나 세로의 길이가 1인 경우에는, 최대 사각형의 크기가 1을 넘을 수 없으므로 해당 처리만 따로 해줍니다. 이 문제의 풀이법이 명확하게 동적 계획법인지 그리디인지는 잘 모르겠습니다. 현재의 가장 최선인 값을 구해가면서 푸는 것이기도 하고 기존에 구했던 해를 메모이제이션 통해 활용하기도 하기 때문입니다. 둘이 섞였나 봅니다.

 

이중 반복문을 돌려 board[i][j]를, 그 위치에서 최대 정사각형의 길이값을 넣어줍니다. 예를 들어보겠습니다.

board[i][j]가 0이라면 계산하지 않습니다. 계산할 필요도 없고 계산하면 안 되죠. (1, 1)을 살펴볼게요. (1, 1)에서 구할 수 있는 최대 사각형은 1 x 1입니다. (0, 0)가 1이었다면 2 x 2가 될 수 있었겠죠. (1, 2)에서는 2 x 2가 가능합니다. 그럼 해당 값을 2로 갱신하겠습니다. 이렇게 끝까지 가보면 값이 다음과 같이 바뀌어요.

규칙을 찾아보면 이렇습니다. [i][j]에서 [i-1][j-1], [i][j-1], [i-1][j]의 위치를 검사합니다. 그림에서 알 수 있듯이 전부 1이면, 2 x 2가 가능하니까 [i][j]를 2로 업데이트할 수 있어요. (2, 2) 위치를 한 번 봅시다. 우리는 직관적으로 (0, 0)가 0이기 때문에 3 x 3이 될 수 없음을 앏니다. 직관은 결과적인 걸 보는 거구요, (0, 0)에 가기 전에 먼저 봐야 알 것은 (1, 1)이 1이라는 점입니다. 만약 (1, 1)이 2였으면 (0, 0)이 1이라는 의미이기 때문에, (2, 2)가 3으로 갱신될 수 있었을 거에요. 즉, 주변 값을 검사할 때 가장 작은 값을 따라 갑니다. 검사해서 가장 작은 값에 1을 더해 현재 위치의 값을 바꿔주면 돼요.

 

코드