목록Dynamic Programming (1)

늘 겸손하게

LeetCode 1277 - Count Square Submatrices with All Ones

안녕하세요 besforyou 입니다 이번 글에서는 LeetCode 문제 1277번 풀이를 써보겠습니다 문제 풀이 방법 1. 그냥 다 찾아보는 방법 정사각형의 개수를 찾아야 하는 문제이다. 우선 m과 n 중 작은 숫자를 min_side라고 하고, 한 변의 길이가 1인 정사각형부터 한 변의 길이가 min_side인 정사각형을 2차원 배열에서 다 찾아본다. 2차원 배열 안에서 인덱스 i, j를 정사각형의 왼쪽 위 꼭지점이라고 가정하고 한 변의 길이가 l이라고 가정하자 그러면 i, j ~ i, j+l / i + l , j ~ i + l , j + l / i , j + l ~ i + l , j + l 안쪽의 숫자가 모두 1이면 정사각형인 것이다. 이를 반복문으로 구현한다. 코드 1 2 3 4 5 6 7 8 9 1..
코딩 문제/LeetCode 2021. 8. 30. 14:03
이전 Prev 1 Next 다음