🌰문제RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.1번 집의 색은 2번 집의 색과 같지 않아야 한다.N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.입력첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같..

🍇문제 🍇풀이방법삼각형 모양의 숫자 배열에서, 꼭대기에서부터 시작하여 아래로 내려오면서 숫자를 더해 나갈 때, 가장 큰 합을 찾는 문제이다. 각 위치에서는 그 위치까지 도달할 수 있는 두 가지 경로가 존재하며, 이전 단계에서 선택된 최적 경로의 값을 고려해야 한다.  이 문제는 Dynamic Programming(동적 계획법)을 사용하여 해결할 수 있다. 각 위치에서 최적의 경로를 선택하여 문제를 해결해보자. 1. DP 테이블 초기화dp = [] for lst in triangle: dp.append([0] * len(lst)) dp 리스트는 삼각형 모양의 구조를 가지며, 각 위치에서의 최댓값을 저장하는 데 사용된다.dp[i][j]는 삼각형의 i번째 행, j번째 열에 위치한 값까지 도달하는 최댓값을 ..

문제* 아래 문제의 recursive property를 제시하라. 3×N 테이블의 각 칸에 양 또는 음의 정수가 기록되어 있다. 조약돌을 놓는 방법 (제약조건)- 각 열에는 적어도 하나의 조약돌을 놓아야 한다.- 가로나 세로로 인접한 두 칸에 동시에 조약돌을 놓을 수 없다. 목표돌이 놓인 자리에 있는 수의 합을 최대가 되도록 조약돌 놓기 합법적인 예 합법적이지 않은 예  문제풀이  다이나믹 프로그래밍 - 행렬의 Column 1">11부터 Column i">i𝑖 까지의 최적해(=최고점)는  Column 1">11부터 Column i−1">i−1𝑖−1 까지의 최적해를 포함하는 구조이기 때문이다.  패턴 분석각각의 Column에 돌을 놓을 수 있는 경우의 수는, 아래와 같이 4가지로 존재한다...

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

Knapsack Problem배낭 문제,Knapsack Problem은 다이나믹 프로그래밍에서 매우 유명한 문제이다. 용량이 K인 배낭에 넣을 수 있는 N개의 물건에 대해 각 물건의 무게 weight와 가치 value가 주어질 때, 배낭에 최대한 가치가 높은 물건들을 담을 수 있는 조합을 찾는 문제이다. 냅색 알고리즘을 나누는 기준담을 수 있는 물건이 나뉠 수 있는가, 없는가? 담을 수 있는 물건이 나누어 질 때 분할가능 배낭문제(Fractional Knapsack Problem) - Greedy 담을 수 있는 물건이 나누어질 수 없을 때 0-1 배낭 문제(0-1 Knapsack Problem) - Dynamic Programming 문제 해결 전략 1. 모든 경우를 탐색하기(Brute Force)N개의..

연쇄 행렬 곱셈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,..