아래 연속된 행렬 곱셈 알고리즘 관련해서 질문드립니다.

조회수 1206회

이미지 이미지

#include <iostream>
using namespace std;

#define MAX 100

int mat_chain_X_DC(int c[], int i, int j) // 분할정복
{
    int min = 2147483647;
    int k, s;
    if (i == j)
        return 0;
    for (k = i; k <= j - 1; k++)
    {
        s = mat_chain_X_DC(c, i, k) + mat_chain_X_DC(c, k + 1, j) + c[i - 1] * c[k] * c[j];
        if (s < min)
            min = s;
    }
    return min;
}


int mat_chain_X_DP(int C[], int n) // 동적 계획법
{
    int S[MAX][MAX], T[MAX][MAX];
    int d, i, j, k;

    for (i = 1; i <= n; i++)
        S[i][i] = T[i][i] = 0;
    for (d = 1; d <= n - 1; d++)
    {
        for (i = 1; i <= n - d; i++)
        {
            j = i + d;
            S[i][j] = 99999;
            for (k = i; k <= j - 1; k++)
                if (S[i][k] + S[k + 1][j] + C[i - 1] * C[k] * C[j] < S[i][j])
                {
                    S[i][j] = S[i][k] + S[k + 1][j] + C[i - 1] * C[k] * C[j];
                    T[i][j] = k;
                }
        }
    }
    return S[1][n-1];
}

int S[MAX][MAX]; // 메모이제이션에 사용될 전역 배열

int Lookup_Chain(int C[], int i, int j)
{

    int min;
    if (S[i][j] < 999999)
        return S[i][j];
    if (i == j)
        S[i][j] = 0;
    else
        for (int k = i; k <= j - 1; k++)
        {
            min = Lookup_Chain(C, i, k) + Lookup_Chain(C, k + 1, j) + C[i - 1] * C[k] * C[j];
            if (min < S[i][j])
                S[i][j] = min;
        }
    return S[i][j];
}

int mat_chain_memoization(int C[], int n)
{
//  int n;
    int min;

    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
            S[i][j] = 999999;

    min = Lookup_Chain(C, 1, n);

    return min;
}


int main()
{
    int size;
    int count = 0;
    int result1, result2, result3;

    cout << "곱셈을 진행할 행렬 갯수 입력" << endl;
    cin >> size;

    int* C = new int[size + 1]; // C의 원소는 행렬수 + 1개

    cout << "-----배열 C(열의 수) 입력----- " << endl;
    for (int i = 0; i < size + 1; i++)
    {
        cout << "C[" << i << "] : ";
        cin >> C[i];
    }

    for (int i = 0; i < size + 1; i++)
        cout << C[i] << endl;

    result1 = mat_chain_X_DC(C, 1, size);
    cout << "결과1 : " << result1 << endl;

    result2 = mat_chain_X_DP(C, size);
    cout << "결과2 : " << result2 << endl;

    result3 = mat_chain_memoization(C, size);
    cout << "결과3 : " << result3 << endl;

    system("pause");
    return 0;
}

이미지

안녕하세요 연속된 행렬 곱셈 알고리즘에 대해 질문좀 드리고자합니다. 연속된 행렬의 곱셈 알고리즘은 연속된 행렬의 최소 곱셈횟수를 구하는 알고리즘입니다.

이에따른 각각의 방법에 대해 곱셈횟수와 실행시간을 구하려고하는데 실행결과를 보니 의문점이 있습니다

제가 공부하기론 연속된 행렬 곱셈 알고리즘은 동적계획법에 적합한 알고리즘이라고 공부를 했습니다. 행렬이 많을수록, 열의수가 많을수록 곱셈연산횟수는 차이가 납니다. 메모이제이션 방법은 동적계획법과 비슷하지만 top-bottom 으로 진행을 하고 또 계산 결과를 저장해 다음번에 또 계산이 필요할때 계산을 하지않고 계산했던 것을 사용하는 방법이라고 들었습니다. 따라서 동적 계획법과 메모이제이션 방법의 곱셈연산의 차이에는 크게 차이가 없을거라고 생각을 했지만

이상하게 사진과 같이 결과1(분할정복) 과 결과3(메모이제이션)의 곱셈횟수는 동일합니다.. 어떻게 된건가요? 메모이제이션 구현은 마지막 사진의 슈도코드를 보고 구현을 했는데 의아하네요 도와주시면 감사하겠습니다

답변을 하려면 로그인이 필요합니다.

프로그래머스 커뮤니티는 개발자들을 위한 Q&A 서비스입니다. 로그인해야 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)