Yepchani's place

문제가장 큰 정사각형 찾기https://school.programmers.co.kr/learn/courses/30/lessons/12905  예시 코드function solution(board) { const n = board.length; const m = board[0].length; const dp = Array.from({ length: n + 1 }, () => Array(m + 1).fill(0)); let maxSide = 0; for (let i = 1; i   풀이표에서 1로 이루어진 가장 큰 정사각형의 넓이를 구하는 문제입니다.dp를 사용해서 풀 수 있습니다. dp[i][j]는 (i, j)를 우하단 꼭짓점으로 하는 정사각형 중 가장 큰 정사각형 한 변의 길이입니다.(i, j)의..

문제동물원https://www.acmicpc.net/problem/1309  풀이2 x N 크기의 우리에 사자를 배치하는 경우의 수를 구하는 문제입니다. 규칙은 다음과 같습니다.사자들을 우리에 가둘 때, 가로 또는 세로로 붙어있게 배치할 수는 없습니다.한 마리도 배치하지 않는 경우도 하나의 경우의 수로 칩니다. DP를 이용해 해결할 수 있습니다. dp[i]는 i번째 우리에 [사자가 없을 때, 좌측에 있을 때, 우측에 있을 때] 입니다.dp[1] = [1, 1, 1]로 초기화 해줍니다. 점화식은 다음과 같습니다. i번째 우리에 사자가 없을 때, dp[i][0]은 i - 1번째 우리의 모든 경우의 수를 합친 값입니다.dp[i][0] = dp[i - 1].reduce((acc, cur) => (acc + cu..

문제1, 2, 3 더하기 4https://www.acmicpc.net/problem/15989  풀이설명정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제입니다. DP를 사용해 해결할 수 있습니다. dp[i]는 i를 1, 2, 3의 합으로 나타내는 방법의 수입니다.dp[0] = 1로 초기화 해줍니다. 1, 2, 3을 num으로 나타낸다면dp[i] = dp[i] + dp[i - num]입니다. 예시 코드function solution() { const T = +input(); const n = 10000; const dp = Array(n + 1).fill(0); const answer = []; dp[0] = 1; for (let i = 1; i

문제  5582번: 공통 부분 문자열두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들www.acmicpc.net 예시 코드function solution() { const str1 = input(); const str2 = input(); const len1 = str1.length; const len2 = str2.length; const dp = Array.from(Array(len1 + 1), () => Array(len2 + 1).fill(0)); let maxLen = 0; for (let i = 1; i  풀이두 문자열에서 LCS(Lo..

문제  2225번: 합분해첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.www.acmicpc.net 예시 코드function solution() { const MOD = 1000000000; const [N, K] = input().split(" ").map(Number); const dp = Array.from(Array(N + 1), () => Array(K + 1).fill(0)); dp[0][0] = 1; for (let i = 1; i = 1) dp[j][i] += dp[j - 1][i]; dp[j][i] %= MOD; } } return dp[N][K];} 풀이이 문제는 DP를 이용해 풀 수 있는데요.이해하는 데 필요한 두 가지 포인트를 알아보겠..