happy coding

수업을 듣고 정리한 내용입니다. Chained Matrix Multiplications 동적계획 알고리즘에서 연속행렬곱셈은 연속된 행렬들의 곱셈에 필요한 원소 간의 최소 곱셈 횟수를 찾는 문제이다. 이 행렬에서 알고리즘은 결합 법칙을 허용하고, 주어진 행렬의 순서를 지켜서 반드시 이웃하는 행렬끼리 곱하도록 합니다. //연속 행렬 곱셈 입력 : 연속된 행렬 A1 * A2 ... * An, 단 A1은 d1 * d2, An = d(n-1) * d(n) 출력 : 입력의 행렬 곱셈에 필요한 원소의 최소 곱셈 횟수 for i = to n C[i,j] = 0 for L = 1 to n - 1 for i = 1 to n - L j = i + L C[i,j] = 무한대 for k = 0 to j-1 temp = C[i,..

수업을 듣고 정리한 내용입니다. Dynamic programming(DP) : 이미 문제가 분할되어 있는 상태로, 입력 크기가 작은 문제들을 해결하기 위해 그 해를 이용해 보다 큰 크기의 부분 문제를 해결하고 최종적으로 원래 주어진 입력의 문제를 해결하는 것이 목표이다. DP vs. 분할 동적 계획 분할 여러 layer를 취합하여 해결한다. 이전 layer를 취합하여 해결한다. 동적 계획 알고리즘은 부분 문제 사이의 의존적 관계가 존재한다. 이는 문제와 입력에 따라 다르고 대부분 뚜렷하다는 함축적 순서를 가지고 있다고 말할 수 있다. 부분 문제의 해는 중복 사용하지 않는다. 최적 부분 구조/ 최적성 원칙 : 문제의 최적해 중 부분문제의 최적해 부분문제들 사이의 관계를 빠짐없이 고려해야 한다. 모든 쌍 최..