✏️문제 ✏️풀이전의 결과를 다음 결과에 이용하게 되는 점화식을 활용한 DP 문제이다. 즉, 메모제이션 방법으로 중복해 계산되는 값을 저장해 계산의 효율을 높일 수 있다. DP로 푸는건 알겠는데, 주어진 N -> 1 로 접근했더니 머리가 아팠다...결국 풀지 못하고 풀이를 참고했고, 상향식(bottom-up) 으로 푸는 것을 알게되었다. X = 10인 경우, 10 -> 9 -> 3 -> 1  과정을 거쳐 1이 되게 되는데9의 경우에는 또, 9 -> 3 -> 1의 과정을 거치며3의 경우에는 3 -> 1의 과정을 거친다.=> 즉, 10을 구할 때는 9의 결과를, 9를 구할 때는 3의 결과를 이용한다.앞에서 구한 결과값을 저장하였다가 후에 사용하는 것이다! 일단, 2와 3으로 나누어 떨어지지 않는 경우는 무조..

문제* 아래 문제의 recursive property를 제시하라. 양 또는 음의 정수 원소들로 구성된 n×n 행렬이 주어지고, 행렬의 좌상단에서 시작하여 우하단까지 이동한다. 이동 방법 (제약조건)- 오른쪽이나 아래쪽으로만 이동할 수 있다.- 왼쪽, 위쪽, 대각선 이동은 허용하지 않는다. 목표행렬의 좌상단에서 시작하여 우하단까지 이동하되, 방문한 칸에 있는 수들을 더한 값이 최소화되도록 한다. 불법 이동 예  유효한 이동의 예  문제풀이 방법 1. 초기화- dp[0][0] = matrix[0][0]: 시작점은 그대로 자신의 값으로 초기화 - 첫 행과 첫 열은 이전 값에 현재 칸의 값(matrix의 값)을 더하여 초기화 (for문) 2. 점화식 dp[i][j] = matrix[i][j] + min(dp[i..

연쇄 행렬 곱셈i × j 행렬과 j × k행렬을 곱하기 위해서는 i × j × k번 만큼의 곱셈이 필요하다.여러 행렬을 곱할 때, 어떠한 행렬 쌍을 먼저 곱하는지에 따라 연산 횟수가 달라진다.   연쇄 행렬 곱셈 동적 계획식 설계 전략재귀 관계식을 이용하여, 이전 단계의 계산을 이후 단계의 계산에 이용할 수 있다.i와 j사이에 있는 특정 값인 k를 사용하여 정답을 찾아간다연쇄 행렬 곱셈에서는 M[i,j] = min{ M[i,k] + M[k+1][j] + d(i-1)d(k)d(j)} 라는 식으로 문제를 해결하는데,i = j이면 이 자체로 하나의 행렬이므로 행렬곱은 0이고,i  ex) i=i , j=2 일 때 -> k=1 (k는 하나) ex) i=1,j=3 -> k=1,k=2 (k는 두 개)-> 이 때, k..

문제어떤 쥐가 p[n][m]로 구성된 미로에 있을 때 왼쪽 아래 즉, p[0][0]에서 시작하여 출구가 있는 p[n-1][m-1]에 도달하려고 한다. 단, 이 쥐는 항상 오른쪽 또는 위쪽으로만 움직일 수 있으며 치즈를 최대한 많이 먹으면서 출구로 이동하여야 한다  풀이방법DP를 활용하여, 문제를 간단하게 풀 수 있다. 여기서 A[i][j]를 i행, j열까지 도달했을 때 먹을 수 있는 최대 치즈의 양이라고 정의하면, 다음과 같은 점화식을 사용하여 문제를 해결할 수 있다 A[i][j] = max(A[i][j-1], A[i-1][j]) + A[i][j]현재 위치에서 왼쪽 칸 또는 위쪽 칸 중에서 더 많은 치즈를 먹을 수 있는 경우를 선택하여 현재 칸까지의 최대 치즈 양을 계산이를 모든 칸에 대해 계산하면, 출..

문제숫자들이 2차원 배열에 있다. 가장 윗 행에서 가장 아래 행까지 내려올때 걸 쳐지는 길에 있는 숫자의 합이 가장 높은것을 찾아보자. 이 때 어느 한 cell에 서 다음 cell로 내려올 경우에는 바로아래, 왼쪽대각선아래, 오른쪽대각선 아 래로만 이동이 가능하다. 풀이방법1. 2차원 배열을 입력받은 뒤, 해당 셀에서 최대 합을 저장할 DP테이블을 만든다.2. 각 셀에서 최대 합 = 현재 값 + MAX( 1번 셀 , 2번 셀 , 3번 셀)3. 위 2번을 반복하여 모든 셀에 대해 최대 합을 계산하고, 가장 아래 행의 최대값이 주어진 문제의 답이 된다.  코드Pythonmatrix = [ [3, 4, 9, -2, 2, 51, -23, 2, -1], [223, 7, 8, -11, 5, -99, 2,..

문제정수 n(2나타낼 수 있는 방법의 수를 구하시오 예를 들어 n=4인 경우는 아래와 같이 5가지이다. 4 = 1+1+1+1 = 2+1+1 = 1+2+1 = 1+1+2 = 2+2  풀이방법1을 구할 때구하는 방식이 1 하나밖에 없으므로, dp[0] = 1로 저장 2를 구할 때구하는 방식은 1+1과 2가 있으므로, dp[1] = 2로 저장 3부터 1과 2의 합으로 표현(dp)3은 1+1+1,1+2, 2+1로 총 3가지가 있는데, 이것을 표현하려고 하면 아래와 같다1 + dp[1] : 방법 2가지2 + dp[0] : 방법 1가지방식을 모두 더한 결과인 3을 새로운 dp[2]에 저장(dp[2] -> 3을 1이나 2의 합으로 표현하는 경우의수가 들어있음) 4를 구할 때이제 응용하면 4를 구할때 부터는 4는 1+..