/ C

알고리즘 정복하기 with C (2)Minimum Multiplication

알고리즘 정복하기 with C (2)Minimum Multiplication

직접 코딩하면서 자료구조 공부하기

개요

자료구조와 알고리즘은 프로그램을 구성하는 가장 핵심적인 요소입니다. 프로그램 개발을 집을 짓는 것에 비유한다면 흙이나 모래, 시멘트, 목재와 같은 자재들이 바로 ‘자료구조’에 해당되고, 이러한 자재들을 이용해서 집을 짓는 것이 ‘알고리즘’에 해당됩니다. 알고리즘은 가장 기본적이고 중요한 부분이기 때문에 복습하는 겸해서 직접 여러가지 알고리즘을 코딩하면서 공부하기로 했습니다.

Minimum Multiplication, Order

최소 곱셈(Minimum Multiplication) 알고리즘은 n개의 행렬을 곱하는데 필요한 기본적인 곱셈의 횟수의 최소치를 결정하고, 그 최소치를 구하는 순서를 결정하는 알고리즘입니다.

입력값은 행렬의 수 n과 배열 d 입니다. 배열 d는 행렬의 크기를 나타냅니다.

출력값은 기본적인 곱셈의 최소치를 나타내는 minmult, 최적의 순서를 얻을 수 있는 이차원 배열 P 입니다. 여기서 P는 행렬 i 부터 j 까지가 최적의 순서로 갈라지는 기점입니다.

최적의 해를 주는 순서의 출력은 Order 라는 알고리즘을 이용합니다.

Minimum Multiplication, Order pseudo code

Minimum Multiplication의 pseudo code

Order pseudo code

Minimum Multiplication 시간 복잡도

for문을 Basic Operation으로 할때 min의 루프까지 3번 중첩되고, j = i + diagonal 이므로, i 루프를 수행하는 횟수는 n - diagonal, k 루프(min)를 수행하는 횟수는 (j - 1) - i + 1 = diagonal 이다. 따라서 ((n - diagonal) * diagonal)에서 diagonal = 1 ~ n-1 까지의 합이므로 n(n - 1)(n +1) / 6 이다. 따라서 O(n^3) 이다.

Minimum Multiplication, Order 구현

입력데이터

소스코드

#include <stdio.h>
#include <stdlib.h>

int minmult(int n, int d[], int* P[]);
void order(int i, int j, int* P[]);     

int main()
{
    //행렬 열 d 배열
    int d[7] = { 30, 35, 15, 5, 10, 20, 25 };
    //행렬 개수
    int number = 6;

    //최적 순서 배열 P생성
    int** P = (int**)malloc(sizeof(int) * 6);
    for (int i = 0; i < 6; i++)
        P[i] = (int*)malloc(sizeof(int) * 6);

    int result = minmult(number, d, P);
    printf("Minimum Multiplication: %d", result); 
    printf("\nM[1][6] Order ");
    order(1, number, P);
    

    return 0;
}

// 최적의 해 순서 출력
void order(int i, int j, int* P[])  
{
    int k;
    if (i == j)
        printf("A%d", i);
    else {
        k = P[i][j];
        printf("(");
        order(i, k, P);
        order(k + 1, j, P);
        printf(")");
    }
}

// 최소 곱 리턴
int minmult(int n, int d[], int* P[])  
{
    int i, j, k, diagnonal, min = 0;
    int tmp = 0;
    int** M = (int**)malloc(sizeof(int) * 6);
    for (i = 0; i < n+1; i++)
        M[i] = (int*)malloc(sizeof(int) * n+1);

    for (i = 1; i <= n; i++)
        M[i][i] = 0;

    for (diagnonal = 1; diagnonal <= n - 1; diagnonal++) 
        for (i = 1; i <= n - diagnonal; i++) {         
            j = i + diagnonal;
            for (k = i; k <= j - 1; k++) {
                M[i][j] = M[i][k] + M[k + 1][j] + d[i - 1] * d[k] * d[j];
                if (k == i) {
                    tmp = M[i][j];
                    min = k;
                }
                else if (M[i][j] > tmp) {
                    M[i][j] = tmp;
                }
                else
                    min = k;
            }
            P[i][j] = min;
        }

    return M[1][n];    
}

결과

최소 행렬 곱셈 알고리즘과 순서 출력을 구현했습니다. 결과가 잘 나옵니다.

알고리즘 진행 과정 손계산

알고리즘의 진행과정을 직접 계산하여 결과를 비교해보았습니다. 결과가 동일하게 나옵니다.