레벨2, 가장 큰 정사각형

1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

현재 도전중인 문제..

너무 많은 경우의 수가 있어서 쉽게 접근을 못하는중..

자괴감 느낀다.. 

# 너무 뻔하게 생각을 해서 그런가 안 풀린다.

1차 완성본.

기본 원리는 첫번째 row에서 1을 검색한다.

그리고 1이 연속되는지 확인 한 후 첫번째 인덱스(start), 끝나는 인덱스(end)를 확인 한다.

그리고 두번째 로우부터 이 인덱스 만큼 슬라이싱 된 리스트만을 확인한다.

이때 첫번째 로우에서 start-end+1 한 값, 즉 한변의 길이를 변수로 저장 한 후

두번째 row에서는 더 작은 값이 나오면 update 한다.(정사각형이므로)

lst = [[0,1,1,1],

       [1,1,1,1],

       [1,1,1,1],

       [0,0,1,0]];

lst2 = [[0,0,1,1],[1,1,1,1]];

위 두가지 경우에 한해서는 통과한다.

# 추가

이 문제가 어려운 이유는 무엇일까? 바로 안되는 경우가 발생 할 경우이다.

아마도, 이 문제를 처음 접하는 사람들은 거진 80-90%는 나 처럼 재귀적 형태로 접근 할 것이라 생각한다.

문제는 재귀적 접근을 하게 된다면 일단 매우 느리게 작동하고, 두번째로 안됫을 경우에 수습을 할라면 다시 처음부터 가야한다.

또한 이런식으로 문제를 풀라면 온갖 경우의 수를 다 생각한 다음 그 경우를 다 해결할 수 있는 코드를 짜야한다.

그렇기에 나온 방법이 동적 프로그래밍이다. 코드가 진행되면서 여태까지의 결과를 저장하는 식으로 간다. 

이렇게 짜게 된다면 굳이 다시 돌아갈 필요도 없고 안되는 경우를 따질 필요가 없다.

이러한 방식을 위에 문제에 적용한다면 이렇게 된다.

우선 최소한의 정사각형 사이즈는 몇일까? 2 * 2 , 즉 4이다.

그렇기에 2 * 2, 총 4칸을 보면 된다.

두번째로 4칸을 볼때 무엇을 봐야할까, 1의 갯수? 아니다. 0의 유무를 확인해야한다.

세번째, 그렇다면 이제 끝난것인가? 다음을 보자

1 1   0 1   0 0  0 0

1 1   1 1   1 0  0 0

위 네가지 경우 중 당연히 제일 왼쪽만이 2 * 2 정사각형이고 나머지는 아니다.

그런데 엄밀히 말하면 2번째, 세번째의 경우에는 아니라기 보단 1 * 1 의 정사각형이다.

그렇다면 다시 두번째로 돌아가서, 우리는 0의 유무를 확인해야만 하고 세번째에서 확인을 했는데 이것을 어떻게 기록해야 할까??

if, else if, else if로 다 돌려야 할까? 이렇게 가능하긴 할 텐데 코드도 복잡하고 암튼.. 그래 ㅎㅎ

포인터(현재 위치한 인덱스)를 제외한 나머지 3개의 최소값을 구하고 그 값에다가 +1 만 하면 된다.

이렇게 하면 굳이 0인지 아닌지도 구분할 필요도 없다(포인터는 구분해야한다 성능 향상을 위해)

위에서 첫번째는 2가 되고 이를 포인터에 기록한다!! (동적 프로그래밍에 핵심)

두번째는 1, 세번째도 1(엄밀히 말하면 패스), 네번째도 패스

# 여기서 포인터를 언급하고 넘어가자면 오른쪽 하단, 즉 (1,1) 위치에 있는 숫자를 포인터로 한다.

왜냐하면 앞서 언급했듯이 정사각형 최소 사이즈는 2*2 이므로 이를 리스트에서 확인하기 위해 굳이 0번째 로우부터 할 필요가 없기 때문이다.

0, 1, 1, 1 -> 이 줄부터 확인 할 필요없고

1, 1, 1, 1 -> 여기 이 줄부터 확인하면 된다. 그것도 저 빨간색부터!

0, 1, 1, 1

다시 원래대로 돌아와서... 최소값을 확인하고 거기에 무조건 1을 더해주면 된다.

1 1   0 1   0 0  0 0

1 2   1 1   1 0  0 0 

위에 얘들은 제일 왼쪽 애만 바뀌고 나머지는 안바뀐다.

그리고 이게 반복된다.

그럼 어느 순간 이런 애가 나타 날 것이다.

ex1)

2,2

2,1 -> 1은 포인터라 아직 동적 할당이 안된 상황

이 의미는 무엇일까 즉, 1로 둘러쌓여져 있던 애들이란 뜻이다.

1, 1 ,1

1, 2, 2

1, 2, 1 

ex1) 의 경우를 넓게 보면 바로 위에 처럼 된 상황인 것이다. 그렇기에 ex1)은 동적 할당으로 3이 된다. 포인터를 제외한 나머지 3개에서 최소값을 찾고 거기에 1을 더해주기 때문에.

마지막으로 위에 4*4 예시를 단계별로 표현하고 마무리 하겠다..

0, 1, 1, 1 

1, 1, 1, 1 -> 최소값이 0이라 +1 해도 어차피 1인 상황

0, 1, 1, 1

0, 1, 1, 1 

1, 1, 2, 1

0, 1, 1, 1

0, 1, 1, 1 

1, 1, 2, 2

0, 1, 1, 1

0, 1, 1, 1 

1, 1, 2, 2

0, 1, 2, 1

0, 1, 1, 1 

1, 1, 2, 2

0, 1, 2, 3