DP 문제. 어렵다

프로그래머스에서 가장 큰 정사각형 찾기 문제를 풀어보는데, 이건 좀 힘들었다.

 

처음 생각한 방식은 for문 두 개를 돌려서 1인 경우를 찾고,

 

만약 1이면 우측과 아래로 한칸씩 늘려가면서 정사각형이 맞나 확인하는 방식이였다.

 

근데 이렇게 하면 for문이 거의 3, 4개가 사용된다. 즉, 복잡도가 O(N3) 이 된다.

 

그래서 이번에는 힌트를 좀 참조했다.

 

DP (Dynamic Programming) 을 사용하는게 가장 좋다고 한다.

 

와. DP 는 학부때도 잘 배운 기억이 잘 안난다.

 

찾아보니 DP, 동적계획법이란게 작은 문제를 모아서 큰 문제를 푸는 것이더라.

 

학부 때 피보나치 수열 푸는 방법을 교수님이 설명해줄때, 이야기 해주셨던 방법 중 하나였다.

 

하나는 재귀함수였고, 다른 함수는 이 동적계획법이였다.

 

당시 동적계획법이라고 말씀해주시진 않았지만, 방식이 이런 방식이였다.

 

검색해서 나온 설명은 큰 문제를 풀기 위해 작은 문제를 풀어 큰 문제를 푸는 방식이라고 한다.

 

보통 이런 방식에는 배열을 많이 사용하여 해당 위치의 값을 저장하여 사용한다.

 

이 문제도 이 방식을 사용해야 한다고 한다.

 

즉, 가장 작은 정사각형인 4개를 계산해서 길이를 누적하여 계산하는 것이다.

 

 

이렇게 누적해가면 최대 길이의 변 길이나 나온다고 한다.

 

만약, 길이가 3인 사각형이라면 다음과 같이 계산 하는 것이다.

 

 

이번 문제는 DP 를 써본적이 없어 여기까지 생각이 닿지 못하였다.

 

아직 수련이 부족하다.