행렬은 수학에서 자주 사용되는 구조로, 정사각형 또는 직사각형 형태의 숫자 배열입니다. 예를 들어 다음은 4행 4열의 행렬입니다:

0 0 1 1 0 1 0 1 0 1 1 1 0 0 0 0

행렬은 세 가지 핵심 요소를 포함합니다: 행의 개수(길이), 열의 개수(너비), 그리고 각 위치에 저장된 값들입니다. 일반적으로 이러한 값들은 2차원 배열로 관리됩니다.

행렬 구조 정의

프로그래밍 상에서는 구조체를 통해 행렬을 쉽게 표현할 수 있습니다.

struct Matrix {
    int rows, cols;
    int data[100][100];
};

여기서 rows는 행의 수, cols는 열의 수이며, data는 실제 값을 저장하는 배열입니다.

행렬의 기본 연산

행렬 덧셈과 뺄셈

두 행렬이 덧셈이나 뺄셈이 가능하려면 반드시 크기가 동일해야 합니다. 즉, 행과 열의 개수가 모두 같아야 합니다.

예를 들어, 두 행렬 A와 B가 다음과 같다면:

A: 1 2 3 4 5 6 7 8 9

B: 5 3 3 4 5 8 9 9 9

이 경우 두 행렬은 모두 3×3이므로 덧셈이 가능합니다. 연산은 각 위치의 값들을 직접 더하거나 빼는 방식으로 이루어지며, 교환 법칙과 결합 법칙이 성립합니다.

결과 행렬은 다음과 같습니다:

6 5 6 8 10 14 16 17 18

이 연산은 간단하여 대부분의 문제에서는 별도로 다루지 않습니다.

코드 구현

Matrix add(Matrix &a, Matrix &b) {
    Matrix result = {a.rows, a.cols};
    for (int i = 1; i <= a.rows; ++i)
        for (int j = 1; j <= a.cols; ++j)
            result.data[i][j] = a.data[i][j] + b.data[i][j];
    return result;
}

행렬 곱셈

행렬 곱셈은 덧셈보다 훨씬 중요한 개념이며, 알고리즘 문제에서 자주 등장합니다.

조건: 행렬 A × B의 곱셈이 가능하려면, A의 열 수(cols)가 B의 행 수(rows)와 같아야 합니다.

계산 방법은 다음과 같습니다:

• 결과 행렬의 (i,j) 요소는, 행렬 A의 i번째 행과 행렬 B의 j번째 열의 대응 항목을 곱한 후 모두 합산한 값입니다.

예시:

A: 1 2 3 4 5 6

B: 3 1 4 2 5 8

A × B 계산 (i=1, j=1):

1×3 + 2×4 + 3×5 = 3 + 8 + 15 = 26

(i=1, j=2):

1×1 + 2×2 + 3×8 = 1 + 4 + 24 = 29

결과 행렬: 26 29 48 62

또한, 결과 행렬의 크기는 (A의 행 수) × (B의 열 수)입니다.

주의사항

행렬 곱셈은 교환 법칙이 성립하지 않습니다. 즉, 일반적으로 A × B ≠ B × A입니다. 하지만 결합 법칙은 성립합니다: (A × B) × C = A × (B × C).

코드 구현

Matrix multiply(Matrix &a, Matrix &b, int mod) {
    Matrix result = {a.rows, b.cols};
    for (int i = 1; i <= a.rows; ++i)
        for (int j = 1; j <= b.cols; ++j)
            for (int k = 1; k <= a.cols; ++k)
                result.data[i][j] = (result.data[i][j] + 1LL * a.data[i][k] * b.data[k][j]) % mod;
    return result;
}

중요 포인트: 중간 계산에서 오버플로우를 방지하기 위해 1LL을 사용하여 64비트 연산을 보장해야 합니다.

행렬의 활용

행렬은 단순한 수치 연산 이상의 역할을 합니다. 특히 행렬 거듭제곱(Matrix Exponentiation)은 피보나치 수열, 그래프 경로 수 계산, 동적 프로그래밍 최적화 등에서 매우 유용하게 사용됩니다.

행렬 곱셈의 효율적인 반복 연산을 위한 알고리즘은 시간 복잡도를 줄이는 데 결정적인 역할을 합니다.