형님들 제가 예전에 2차원 배열 내에서 가장 큰 직사각형 구하는 문제를 도전 한 적이 있거든요?
요즘에 코드를 다시 봐서 풀어볼라고 하는데, 무슨 알고리즘인지 몰라서 그런데 알려주실 수 있을까요?
예를들어 2차원 배열에서, 0으로 이루어진, 가장 큰 직사각형 구하기.
입력 방식)
H W
s...1
s...2
...
s...H
입력 예 1)
4 5
01100
00000
00011
10111
출력 예 1)
6
이런식으로...
내가 도전? 했을 때는 for문 6중첩을 해서... 실패한 적이 있읍니다.
for i : 왼쪽 위 꼭짓점의 x좌표 --for j : 왼쪽 위 꼭짓점의 y좌표 ----for k : 정사각형 한 변의 길이 ------if 정사각형이 범위 안에 있고 모두 '0'이면 --------답 update
시간 초과면 다르게 풀어야됨
O(n^2), 히스토그램에서 가장 큰 직사각형 맞나..
ㄴㄴ 댓글에 달음
슬라이딩 윈도우 느낌나는데
해당 댓글은 삭제되었습니다.
이건 열의 순서를 바꿀수 있다는데? 아예 다른 문제 아니노
ㄴ잘못 가져와서 다시 달았음
https://www.acmicpc.net/problem/11873
작성자가 아닌가..? 여튼 N^2잘 돌아가겠네
아 N^3은 안되는구나..
https://www.acmicpc.net/problem/3321
이 문제 같은데
아 이건 열 바꿀 수 있구나
정사각형이지만 비슷한 문제는 dp풀이더라
https://www.acmicpc.net/problem/1915
이거 정사각형은 대놓고 dp긴한데
가로로만 dp 세로로만 dp하고 둘이 합치면 시간초과뜸?
아랫변고정하고 히스토그램 만들어서 하면 제곱에 됨