[파이썬/Python] 동적 프로그래밍 - 행렬 곱셈 순서 계산하기 ( Brute-Force Algorithm )

동적 프로그래밍 - 행렬 곱셈 순서 계산하기 ( Brute-Force Algorithm )

---

서론

동적 프로그래밍(Dynamic Programming)은 최적 부분 구조(Optimal Substructure)를 가지고 있고, 재귀 호출 시 비효율적인 중복이 발생하는 경우(Overlapping Recursive Calls) 사용하면 효과적이다.

 

최적 부분 구조(Optimal Substructure)란 큰 문제의 최적 솔루션에 작은 문제의 최적 솔루션이 포함되는 것을 말한다.

 

동적 프로그래밍을 적용하기 위해 항상 최적 부분 구조를 갖고 있는지 먼저 확인해야 한다.

 

그렇다면, 대표적인 동적 프로그래밍 문제로 행렬 곱셈 순서에 대해 동적 프로그래밍을 적용해보자.

---

본론

i × j 행렬과 j × 행렬을 곱하기 위해서는 일반적으로 i × j × k 번 만큼의 기본적인 곱셈이 필요합니다.

 

다음의 예제를 보자.

연쇄적으로 행렬을 곱할 때, 어떤 행렬 곱셈을 먼저 수행 하느냐에 따라서 필요한 기본적인 곱셈의 횟수가 달라지게 됩니다.

따라서, 행렬을 연쇄적으로 곱할 때 기본적인 곱셈의 횟수가 가장 적게 되는 최적의 순서를 결정해야 합니다.

 

우선, 행렬 곱셈 순서 문제가 최적 부분 구조를 지니고 있는지 확인해야 합니다.

 

예를 들어, 6개의 행렬을 곱한다고 가정할 때 최적해가 다음과 같다면,

3개의 행렬(A2, A3, A4)을 곱하는 최적의 순서는 다음과 같습니다.

n개의 행렬을 곱하는 최적의 순서는 n개의 행렬 중 일부 부분집합에 속하는 행렬을 곱하는 최적의 순서를 항상 포함합니다.

따라서, 행렬 곱셈 순서 문제는 최적 부분 구조를 지니고 있습니다.

 

그렇다면 바로 문제로 들어가보겠습니다.

 

문제. 연쇄 행렬들의 곱인 A1 × A2 × A3 × A4 × A5를 계산하는 최적순서와 그 비용을 구하라.

● 재귀적 관계 도출

- C1,5 : A1 부터 A5 까지의 행렬을 곱하는데 필요한 곱셈의 최소 횟수

- 예를 들어, C1,5 를 구하기 위하여 다음과 같이 두 개의 부분으로 나누어서 계산한다고 생각하며, 두 부분으로 나누는 각 경우에 대해 가장 적은 곱셈 횟수를 산출하는 경우만을 선택합니다.

 

따라서 최적의 순서는 다음과 같이 정의됩니다.

 

이를 브루트-포스 알고리즘(Brute-Force Algorithm)을 이용하여 행렬 M에 값을 계단식으로 대입해보는 과정을 통해 문제를 해결합니다.

 

1. k = 1 : 대각선1

 

 

2. k = 2 : 대각선2

 

3. k = 3 : 대각선3

 

4. k = 4 : 대각선4

 

5. k = 5 : 대각선5

따라서, 최적의 순서 C1,5 = C1,4 + C5,5 + p0 × p4 × p5 이고, 비용은 1320 입니다.

---

결론

동적 프로그래밍(Dynamic-Programming)을 사용하면 연산을 훨씬 빨리 수행할 수 있다는 사실을 직접 연산을 통해 느낄 수 있었습니다.

만약 동적 프로그래밍을 적용하지 않았다면, 연산 하나 하나를 다시 반복하여 수행하는데 시간이 오래 걸렸을 것입니다.

나중에 함수를 재귀적으로 호출할 경우가 생긴다면, 최적 부분 구조 검사를 통해 동적 프로그래밍을 적용할 수 있겠습니다.

특히 행렬의 곱셈이 순서에 따라 연산횟수가 천차만별이라는 사실도 처음 알았고, 유용하게 쓸 수 있을 것 같습니다.