DP

[Java] 프로그래머스 Lv2 - 2 x n 타일링

🔗 문제링크 코딩테스트 연습 - 2 x n 타일링 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 programmers.co.kr 📂 분류 DP 💡 풀이 2 x n 타일링 문제는 메모이제이션을 대표하는 문제이다. 이 문제는 bottom-up 방식과 top-down 방식 두 가지로 해결할 수 있는데, 나는 bottom-up 방식으로 접근하여 문제를 해결했다. 접근 방식 n이 1일 경우 가로로만 배치할 수 있기 때문에 배치할 수 있는 경우는 한 가지만 존재한다. n이 2일 경우 가로로 배치하고 세로로도 배치할 수 있기 때문에 배치할 수 경우는 두 가지가 존재한다. n이..

[Java] 프로그래머스 Lv2 - 가장 큰 정사각형 찾기

🔗 문제링크 코딩테스트 연습 - 가장 큰 정사각형 찾기 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr 📂 분류 DP 💡 풀이 DP Bottom-up 방식으로 해결되는 문제이다. 접근방식 정 사각형의 넓이를 구하는 문제이기 때문에 왼쪽, 위쪽이 하나라도 0이라면 넓이는 1이 된다. 따라서 점화식은 아래와 같이 나온다. cache[i][j] = Math.min(cache[i - 1][j - 1], Math.min(cache[i - 1][j], cache[i][j - 1])) + 1; 💻 코드 public class Solution { private int[][] cache; public int solution(int[][] board) { in..