[ 해결 방법 ]
1. DP 알고리즘 활용
2. 위치한 값이 1일 때, [ 왼쪽 / 왼쪽 위 대각선 / 위쪽 ] 의 값을 확인해 가장 작은 값에 +1 해준다.
DP 알고리즘
- DP 사용 조건
1) 겹치는 부분 문제 : 동일한 작은 문제들이 반복하여 나타나는 경우에 사용이 가능하다.
ex. 이진 탐색과 피보나치 수열
이진 탐색 : 정렬된 배열 내에서 그 위치를 바로 찾기 때문에 재사용 과정을 거치지 않아 DP 사용 조건에 해당하지 않는다.
피보나치 수열 : f(n) = f(n-1) + f(n-2) 이므로, 트리구조로 동일한 부분 문제가 중복되어 나타나 DP 사용 조건에 해당한다.
2) 최적 부분 구조 : 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우
ex. 최적 경로 문제
여러 경로 중 [ A-X, X-B ] 가 가장 짧은 경로라면 A-X-B 가 정답이 된다.
이와 같이 부분 문제의 최적의 결과가 전체 문제에서도 동일하게 적용되어 결과가 변하지 않는 경우 DP를 사용할 수 있다.
- DP 사용 과정
1) DP로 풀 수 있는 문제인지 확인
2) 변수 간 점화식 만들기
3) Memoization
: 변수의 값에 따른 결과를 저장하는 것을 메모라고 부른다. 보통 배열을 사용하며, 1~3차원 배열이 될 수 있다.
5) 기저 상태 파악하기
: 가장 작은 문제의 상태를 파악해야 한다.
6) 구현하기
Bottom-Up ( 반복문 - Tabulation )
아래에서부터 계산을 수행해 누적시켜 전체 큰 문제를 해결하는 방식
Top-Down ( 재귀 - Memoization )
위에서부터 바로 호출하며 결과 값을 재귀를 통해 전이시켜 재활용하는 방식
[ 문제 코드 ]
- Tabulation 방식으로 해결
public class 가장큰정사각형찾기 {
/**
* TODO
* - 목표: 가장 큰 정사각형을 찾아라
* - DB 알고리즘 활용
장 * **/
public static void main(String[] args) {
int[][] arr = {{0, 0, 1, 1}, {1,1,1,1}};
int solution = solution(arr);
System.out.println(solution);
}
public static int solution(int [][]board)
{
int answer = 0;
int[][] map = new int[board.length + 1][board[0].length + 1];
int maxLen = 0;
for (int i = 1; i <= board.length; i++) {
for (int j = 1; j <= board[0].length; j++) {
if(board[i-1][j-1] != 0) {
int min = Math.min(Math.min(map[i - 1][j], map[i][j - 1]), map[i - 1][j - 1]);
map[i][j] = min + 1;
maxLen = Math.max(maxLen, min + 1);
}
}
}
return maxLen * maxLen;
}
}