반응형
가장 큰 정사각형 찾기
-
프로그래머스 Lv.2) 가장 큰 정사각형 찾기알고리즘/프로그래머스 2020. 5. 19. 23:01
가장 큰 정사각형 찾기 코딩테스트 연습 - 가장 큰 정사각형 찾기 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr 풀이 DP를 이용해 이 문제를 풀었다. Top-down을 이용해서 풀었고, board를 돌면서 어떠한 점이 1이라면 그 점을 기준으로 왼쪽, 왼쪽 상단, 상단 세 점의 최소값을 찾아 1을 더해줬다. 이후에 max값을 갱신했고, 탐색이 끝난 후에는 max값의 제곱을 리턴해주었다. 1. board의 모든 점을 탐색한다. 2. board가 1이라면 해당 점을 기준으로 좌측, 좌측 상단, 상단 세 점의 최소값을 찾는다. 2.1 최소값에 +1을 해주어 해당 점에서 만들 수 있는 정사각형의 최대 크기를 저장해주었다. 3. 2번이 끝난 후 m..