🌰문제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번째 열에 위치한 값까지 도달하는 최댓값을 ..

✏️문제 ✏️풀이전의 결과를 다음 결과에 이용하게 되는 점화식을 활용한 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으로 나누어 떨어지지 않는 경우는 무조..

TSP (외판원 문제) 란? home city에서 출발해 모든 city를 한번씩 거치고 다시 home city로 돌아오는 최단 경로를 구하는 문제이다. 즉, 아래와 같이 문제를 생각할 수 있다. 어떤 외판원이 n개의 도시를 방문할 계획을 수립하고 있다고 가정하자. 각 도시는 다른 모든 도시와 도로로 연결되어 있다. 출장 비용을 최소로 줄이기 위하여 외판원이 거주하고 있는 도시에서 각 도시를 한 번씩만 방문하고 다시 출발한 도시로 돌아오는 가장 최소 비용의 일주여행 경로를 찾고자 한다.  그림과 같이 각 도시의 위치가 표시된 미국 지도가 있다. 각 도시를 한 번씩 방문한다고 했을 때, 어떤 순서로 방문해야 가장 짧은 거리가 될까? (n - 1)! 즉 O(n!)이라는 결과가 나온다. 이렇게 비효율적인 방법은..

문제* 아래 문제의 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..