최적의 행렬 곱셈

https://programmers.co.kr/learn/courses/30/lessons/12942

코딩테스트 연습 - 최적의 행렬 곱셈

난이도 : Level 4

잡동사니 : 최적의 행렬 곱셈 관련 많은 풀이들이 있는데 굳이 이 글을 작성하게 된 이유는 설명이 잘되어 있음에도 난 도대체 이해가 안돼서 멘붕이 왔다.

약간 오기도 생겨서 풀릴 때까지 풀어보잔 식으로 들이 파기 시작했다.

 

연쇄 행렬 최소곱셈 알고리즘에 대한 설명이 잘되어 있어 이해가 된 것 같았는데 정작 코드로 옮겨지지가 않았다. (완전히 이해도 못했고 점화식이란 말도 어디서 들어본 듯 하기만 하고 잘 이해가 안 되었다. )

점화식(漸化式) : 수열에서 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식

 

그럼에도 이해가 가지 않는 다면 나와 비슷한 경험을 하신 분이기에 아래 글들이 의미가 있기를 바란다.

 

우선

1. 두 행렬의 연산 횟수 계산
예) [3,4] X [ 4,1] = [3,1]
3 * 4 * 1 = [3,1] 의 연산 횟수

인데 이것을 프로그래머스  C++  문제를 예시로 수식을 작성해 보겠습니다.

예시 값	제공
[[5,3],[3,10],[10,6]]	vector<vector<int>> matrix_sizes

위 예시값이 int 타입의 vector에 vector로 제공되고 있습니다.

위 예시로 값을 확인해 보면

[5,3],[3,10] 행렬의 곱셉의 경우는
5 * 3 * 10 = 150 이 두행렬의 연산 횟수가 됩니다.

코드로 보면 
matrix_sizes[0][0] * matrix_sizes[0][1] * matrix_sizes[1][1] 혹은
matrix_sizes[0][0] * matrix_sizes[1][0] * matrix_sizes[1][1] 로 됩니다.
(matrix_sizes [1][1]의 의미는 마지막 행렬의 열의 값을 의미함)

하지만 위에 코드는 안 되는 이유가 더 많은 행렬이 존재하고
예) A[5,3],B[3,1],C[1,4],D[4,2]

이들의 결합이 (A,B)(C,D) 일 경우
5 * 1 * 2 가 되어야 하는데 위 코드대로 라면 5 * 3 * 2 가 되어 버리기에 
matrix_sizes [1][0]의 의미도 다음 행렬의 행의 값이라기 보단
곱셈이 되는 첫 번째 행렬의 행의 값이 된다.

더 이해하기 쉽게 정리를 하면
matrix_sizes[첫행렬][행] * matrix_sizes[곱셈이 되는 행렬][행] * matrix_sizes[마지막 행렬][열]로 되고
아래와 같은 수식이 만들어집니다.
matrix_sizes[start][0] * matrix_sizes[sp+1][0] * matrix_sizes[end][1]
* sp : split point

 

예시의 값은 3개의 행렬 곱셈인데 좀 더 행렬을 늘려서 생각해보자.

ABCDE 행렬이 있다면 어떤 행렬의 곱이 가장 적게 연산하는지 확인하기 위해서는 가장 작은 부분의 행렬곱부터 전체 행렬 곱까지 연산 횟수를 전부 알고 있어야 가장 적은 연산횟수를 찾을 수 있다.

우선
1) 두 개의 행렬 곱셈의 값이 필요하고
(AB)
(BC)
(CD)
(DE)
2) 다음은 세 개의 행렬 곱셈의 값
A(BC)
(AB)C
B(CD)
(BC)D
C(DE)
(CD)E

3) 다음은 네 개의 행렬 곱셈의 값
A(BCD)
(AB)(CD)
(ABC)D
B(CDE)
(BC)(DE)
(BCD)E

4) 다음은 다섯 개의 행렬 곱셈의 값
A(BCDE)
(ABCD)E

조금 감이 오나요? 4) 행렬에서 BCDE 혹은 ABCD 의 값은 3)에서 여러 가지 행렬곱의 경우에서 최소 연산 횟수를 찾은 결과에 A 혹은 E를 곱한 경우로 이 결과값이 우리가 찾는 최소 연산 횟수 AE가 된다. 
좀 더 설명하면 3)의 BCD 혹은 CDE는 2)에서 최소 연산 횟수가 구해진 값이 있고, AB, CD, BC, DE의 연산 횟수는 1)에서 이미 구해진 값이 있기에 모두 더한 AE의 값 중 가장 작은 값을 리턴하면 된다.

위와 같은 계산을 하는 점화식의 수식은 아래와 같다.

*DP[i][j] : I * J 행렬곱을 했을 때 최소 연산 횟수를 저장하는 배열

1) 두 개의 행렬 곱셈의 값
(AB)의 경우 : 연속적인 계산을 하기 위한 숫자로 표현하면 A행렬은 첫 번째 이기에 0, B행렬은 두 번째 이기에 1로 표현할 수 있고, 이것의 행렬곱의 연산 횟수는  DP[0][1] 에 저장하면 되고 이 값은 아래와 같이 표현 가능하다.
DP[0][1] = [0,0] + [1,1] + (matrix_sizes[0][0] * matrix_sizes[1][0] * matrix_sizes[1][1])
L 여기서 표현하는 i와 j 같은 [0,0] 혹은 [1,1]은 자기 자신을 의미한다. 위 수식을 영문으로 표기하면
DP[A][B] = A + B + AB에 해당한다. 당연히 A와 B는 행렬 곱한 형태가 아니니 연산 횟수는 '0'이 된다. 해서 실질적으로 여기서는  DP[A][B] = AB 이렇게 되는 것이다. 
다른 값도 마찬가지이니 점화식 로직에 들기 전에 이에 해당하는 값들은 전부 0으로 세팅도 필요하다.

for ( int i = 0 ; i < sizes ; i++ )
    dp[i][i] = 0;

(BC)의 경우는 
DP[1][2] = [1,1] + [2,2] + (matrix_sizes[1][0] * matrix_sizes[2][0] * matrix_sizes[2][1])
CD, DE 도 동일한 형태이다.
(CD)
(DE)
2) 다음은 세 개의 행렬 곱셈의 값
A(BC)의 경우 : DP는 ABC의 행렬 곱 이므로 숫자로 표기하면 DP [0,2]가 된다. BC를 먼저 곱하고 A를 곱하는 순으로 되어 있으니 수식 표현은 아래와 같다.
DP[0][2] = [0,0] + [1,2] + (matrix_sizes[0][0] * matrix_sizes[1][0] * matrix_sizes[2][1])
[0,0] 은 0이고 , [1,2] 은 1)에 BC에서 이미 계산된 값이 있기에 이 값과 합성곱 값을 더한 값으로 DP[0][2] 을 구한다. 하지만 아래 (AB)C 와 같은 형태도 있기에 둘중 더 낮은 값을 사용하기 위해 std::min() 함수를 이용하여 더 작은 값을 DP[0][2] 에 저장한다.
DP[0][2] = min(DP[0][2], DP[0][0] + DP[1][2] + (matrix_sizes[0][0] * matrix_sizes[1][0] * matrix_sizes[2][1]))
(AB)C
B(CD)
(BC)D
C(DE)
(CD)E

이렇게 3), 4)까지 가다 보면 일정한 규칙을 발견할 수 있게 된다.

DP[0][1] = min(DP[0][1], DP[0][0] + DP[1][1] + (matrix_sizes[0][0] * matrix_sizes[1][0] * matrix_sizes[1][1]))
DP[1][2] = min(DP[1][2], DP[1][1] + DP[2][2] + (matrix_sizes[1][0] * matrix_sizes[2][0] * matrix_sizes[2][1]))


DP[0][2] = min(DP[0][2], DP[0][0] + DP[1][2] + (matrix_sizes[0][0] * matrix_sizes[1][0] * matrix_sizes[2][1]))
시작 행렬
끝 행렬
변하지 않는 값
행렬과 행렬이 곱해지는 기준점
행렬과 행렬이 곱해질 때 뒷 행렬 = 행렬과 행렬이 곱해지는 기준점 + 1

위 값들을 수식으로 표현하면 
DP[start][end]
= min(DP[start][end], DP[start][sp] + DP[sp+1][end] + (matrix_sizes[start][0] * matrix_sizes[sp+1][0] * matrix_sizes[end][1]))

이렇게 점화식을 도출할 수 있게 된다. 나머지는 기본 코드와 for을 넣어서 진행을 하면 아래와 같은 코드가 나온다.

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<vector<int>> matrix;
int dp[201][201];

/**
* sol() 행렬 합성 곱 최소 연산 갯수 리턴 함수
* param {int} 행렬 곱셉의 갯수
*/
int sol(int sizes) {
    for ( int i = 0 ; i < sizes ; i++ )
    {
        dp[i][i] = 0;
    }
    for ( int i = 1 ; i < sizes ; i++ )
    {
        int end;
        for ( int start = 0 ; start < sizes ; start++ )
        {
            end = i + start;
            
            if(end >= sizes) break;
            
            dp[start][end] = 2e9;
            //sp : split position
            for ( int sp = start ; sp < end ; sp++ )
            {
                dp[start][end] = 
                    min(dp[start][end], dp[start][sp] + dp[sp+1][end] +
                        (matrix[start][0] * matrix[sp+1][0] * matrix[end][1]));
                cout << "i = " <<  i << " start = " << start << " end = " << end << " sp = " << sp << endl;
                cout << "dp[start][end] = " << dp[start][end] << "\t" << endl;
            }
            cout << endl;
        }
    }    
    
    return dp[0][sizes-1];
}

int solution(vector<vector<int>> matrix_sizes) {
    matrix = matrix_sizes;
    int answer = sol(matrix_sizes.size());
    cout << "result = " << answer << endl;
    return answer;
}

 

프로그래머스에서 실행을 하면 모두 TC에서 통과를 하고 아래와 같은 결과 같이 나온다. 정상적으로 처리된 듯하다.

이 점수가 무슨 의민지 아직 모르겠다 ㅡㅡ;

PS. 제가 이해한 내용을 나름 이해할 수 있게 정리한다고 했는데 혹시나
궁금한 게 있으시면 댓글 남겨주세요.
더 글에 살을 채워가겠습니다.