Largest Submatrix With Rearrangements 썸네일형 리스트형 [Greedy]Leetcode 1727, Largest Submatrix With Rearrangements 간만에 정말 재미있게 푼 문제다. 언제나 이야기 하듯이 Greedy 문제는 접근 방법을 생각하지 못하면 접근이 어렵다. 이 문제는 어떻게 접근해야 할까? 아래의 사실을 주의 깊게 생각해 한다. 1) Matrix의 크기가 $10^5$ 이하다. 계산량을 따져보았을 때 O(n), O(nlogn) 접근법을 떠올려야 한다. 2) Column 방향으로는 원소가 변화하지 않는다. column의 순서가 low 방향으로만 변화할 뿐이다. 3) Matrix에 접근할 때 접근 방법으로 현재 row 보다 큰 row 방향으로만 직사각형 넓이를 생각한다. 모든 row에 대한 탐색이 이루어 지기 때문에 위의 접근법은 유효하다. 접근 방법을 생각해 보자. 위의 사실을 유념해 두고 아래와 같이 column방향으로 1이 연속적으로 있을.. 더보기 이전 1 다음
