![[알고리즘] 동적 계획법 | 연쇄 행렬 곱셈](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FxFBYM%2FbtrRSRctyN5%2FRinBhvmO60QQV1k5MafDt0%2Fimg.png)
동적 계획법을 복습할겸 연쇄 행렬 곱셈에 대해 다시 한 번 정리하고자 한다.
연쇄 행렬 곱셈 문제가 뭔데?
주어진 n 개의 연쇄 행렬을 곱하는 최적의 순서를 구하시오.
n 개의 연쇄 행렬 곱셈: A1 * A2 * ...* An [행렬 곱셈은 결합 법칙이 성립한다!]
예를 들어, (Ax * Ay) * Az = Ax * (Ay * Az) 이렇게 곱셈 순서를 바꾸어도 계산 결과가 같다는 뜻이다.
그러나 중요한 점은 행렬 곱셈의 순서에 따라 각 원소의 곱셈 횟수가 달라진다는 것이다.
그렇다면 최적의 순서는 곱셈의 횟수가 가장 작아지도록 하는게 최적일 것이다.
즉 이 문제는 최적화 문제라는 뜻이다. -> 원소의 곱셈 횟수를 최적화하는 문제를 찾아보도록하자.
연쇄 행렬 곱셈 문제를 이해해보자!
2 * 3 행렬과 3 * 4 행렬을 곱하면 2 * 4 행렬이 나온다.
원소를 곱하는 횟수는 2* 3* 4 = 24가 된다.
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0
일반적으로 i * k 행렬과 k * i 행렬을 곱하면 i * j 행렬이 나온다.
원소 곱셈의 횟수 i * k * j
1. 직선적 알고리즘(단순 무식하게 풀기) : 모든 경우의 수에 대해 계산해 보고 최적의 순서를 선택한다.
연쇄 행렬이 4 개일경우 다섯 가지 경우의 수가 존재한다. 모든 경우의 수를 다 계산해보고
최소값을 구하는 방법이 있는데 이는 지수시간이 걸리기 때문에 굉장히 비효율적이다.
연쇄 행렬 곱셈의 엄밀한 정의
n 개의 연쇄 행렬 곱셈 : A1 * A2 * ...* An
A k-1 의 행의 개수와 A k의 열의 개수가 같아야한다.
dk를 행렬 Ak의 행의 개수로 정해야 한다.( 1<= k = n)
2. 동적 계획법을 사용한 알고리즘
연쇄 행렬 곱셈에 동적 계획을 적용할 때의 단계는 다음과 같다.
1) 재귀 관계식을 찾는다.
M: 연쇄 행렬을 곱하는데 필요한 곱셈의 최소 회수 행렬
M[i][j]: Ai 에서 Aj까지 행렬을 곱하는데 필요한 곱셈의 최소 회수(1 <= i <= j <= n)
우리가 할일은 이 행렬을 분할하는 재귀 관계식을 찾는 것이다.
2) 상향식 방법으로 해답을 구한다.
1. 초기화한다. M[i][i] = 0 ( 주 대각선을 0으로)
2. 최종 목표는 M[1][n]이다.
3. 상향식으로 계산한다. 예를 들어 대각선 1번, 대각선 2번,...대각선 n-1번
그럼 재귀 관계식은 어떻게 찾는가?
- 분할정복을 이용한다. n개의 행렬을 두 개의 최적 부분행렬의 곱으로 분할한다.
-각 분할의 곱셈 횟수: 각 부분행렬의 곱셈횟수 + 두 행렬의 곱셈 횟수
= M[1][k] + M[k+1][6] + d0dkd6
최적 분할:
연쇄 행렬 곱셈의 재귀관계식:
이 식을 이해하면 구현단계로 넘어갈 수 있다!
아무튼 위에 있는 재귀 관계식을 이용하여 위 표를 전부 채워보자!
곱셈 순서는 재귀 호출을 통해 분할 정복을 하면 된다.
'전공 수업 CS > algorithms' 카테고리의 다른 글
| [알고리즘] 동적계획법 | 스트링 편집 거리(String edit distance) (0) | 2022.11.25 |
|---|---|
| [알고리즘] 동적계획법 | 최적 이진 탐색 트리 (1) | 2022.11.25 |
| [알고리즘] 동적 계획법 | 행렬의 연쇄적 곱셈 | 연쇄 행렬 최소곱셈 알고리즘 (0) | 2022.11.22 |
| [알고리즘] 욕심쟁이 알고리즘 | 그리디 알고리즘(Greedy Algorithm)동적 계획법을 공부하다가 궁금해진 알고리즘 (0) | 2022.11.16 |
| [알고리즘] 동적 계획법 | 다이나믹 프로그래밍 ( Dynamic Programing) (0) | 2022.11.16 |