dp1

• [Algorithm] 백준 4095번(BOJ 4095) 최대 정사각형 문제풀이!!(Java) 안녕하세요 Coding-Knowjam입니다. 오늘은 백준 온라인 저지에 있는 4095번 최대 정사각형 문제를 풀어보겠습니다. 문제에 대한 링크는 아래에 있으니 문제를 먼저 읽고 와주시길 바랍니다. https://www.acmicpc.net/problem/4095 1. 문제 설명 해당 문제는 다이내믹 프로그래밍 유형으로 문제를 풀기 위해서 점화식을 도출해야 합니다. 사실 대부분의 DP문제가 점화식만 도출하면 코드 작성은 간단한데, 이번 문제도 다르지 않습니다. 주어진 2차원 배열의 최대 정사각형의 크기를 map[i][j]로 가정하면 점화식은 다음과 같습니다. map[i][j] = min(map[i-1][j-1], map[i-1][j], map[i][j-1]) + 1 즉, 2차원 배열의 좌측 대각선, 좌측,.. Algorithm & Data Structure/문제풀이 2021. 10. 19.