[Linear Algebra] #36~38. 행렬식의 여러가지 성질 · 효율적 계산 · 행렬식의 곱

다이나믹 프로그래밍 적용 문제 (4) 최장 공통 부분순서 LCS 문제 설명 부분순서와 공통 부분순서의 예시는 다음과 같다. 는 문자열 의 부분순서. 는 문자열 와 의 공통 부분순서. 최장 공통 부분순서(Longest Common Subsequence)란 공통 부분순서들 중 가장 긴 것을 말한다. 예를 들어, 다음 두 문자열의 LCS를 구하면 다음과 같다. h e r o i c a l l y s c h o l a r l y 결과 문자열 : holly, LCS : 5 주어지는 두 문자열의 LCS를 구하라. 점화식 LCS(i, j) : 문자열 X[i] = "x1,x2, … ,xi" 과 Y[j] = "y1,y2, … ,yj" 의 LCS 길이 LCS(i, j) = { 0 ( if i = 0 or j = 0 ) L..

[Linear Algebra] #33~35. 행렬식과 여러가지 성질들

[Linear Algebra] #30~32. LU분해② · LU분해③ · LU분해④

[Linear Algebra] #28~29-1. 해집합의 성질③ · LU분해① · 대각 행렬의 거듭제곱

다이나믹 프로그래밍 적용 문제 (3) 행렬 곱셈 순서 문제 설명 행렬 A1, A2, A3, . . . , An을 곱하는 수를 최소로 하는 최적의 곱셈 순서를 구하라. 예로, 행렬 A(2 × 3), B(3 × 5), C(5 × 2)가 있을 때 곱할 수 있는 경우의 수는 다음과 같다. (AB)C = 2 × 3 × 5 + 2 × 5 × 2 = 50 A(BC) = 3 × 5 × 2 + 2 × 3 × 2 = 42 두 경우의 수에서 최솟값인 42에 해당하는 연산이 최소의 곱셈 횟수 42와 최적의 곱셈 순서 A(BC) 가 된다. 마지막 행렬 곱셈이 수행되는 상황을 다음과 같이 정리할 수 있으며, 경우의 수는 총 n - 1이다. 점화식 Ak의 크기 : pk-1 * pk m[i, j] : 행렬 Ai, …, Aj의 곱을 ..