[CLRS] [4-1] Multiplying square matrices(행렬 곱)

1.Introduction

- Chapter4 부터는 분할 정복(Divide & Conquer) 응용을 살펴보고, 

- 분할 정복 알고리즘을 분삭할 때 생기는 점화식을 딥하게 알아보고자 한다.

 

1.1. 분할 정복(Divide & Conquer)

- 주어진 문제를 재귀적으로 해결한다.

- Base case(Bottoms Out) 같은 경우 재귀 없이 직접 해결 하고

- Recursive case같은 경우 다음과 같이 세가지 단계로 나누어 문제를 해결한다

 

1) Divide(분할) : 문제를 더 작은 동일 문제의 하위 문제로 나눔

2) Conquer(정복) : 하위 문제를 재귀적으로 해결함

3) Combine(결합) : 하위 문제의 해결책을 결합하여 원래 문제의 해결책을 만듬 

 

1.2. Recurrences(점화식)

- 재귀적 분할 정복 알고리즘을 분석하기 위해선 점화식에 대해서 알아야 한다.

- 점화식(Recurrence)는 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식이다.

- 재귀 알고리즘의 실행 시간을 수학적으로 설명할 수 있게 하는 매개체가 될 수 있다.

 

1.3. 알고리즘 점화식

- 알고리즘 점화식이 무엇인지 알아보자.

- 점화식 T(n)이 알고리즘적이라는 것은 , 충분히 큰 n0 > 0 에 대해 다음 두 가지 속성을 성립 할 때를 의미한다.

1. 모든 n < n0에 대해, T(n)  = O(1) 를 갖는다.

2. 모든 n >= n0에서, 재귀의 모든 경로는 유한한 수의 재귀 호출 내에서 정의된 Base case에서 끝난다. 

 

2. Multiplying square matrices(행렬 곱)

- 행렬곱을 구현해보자.

- 행렬 곱은 다음을 만족시킨다. 

 

 

- m x n 행렬과 n x l행렬의 곱은 m x l 행렬이 된다.

 

- A,B를 전부 n x n 정사각행렬이라고 가정하자, 그러면 C도 마찬가지로 n x n 정사각행렬이 된다.

 

- n x n 행렬 A,B,C를 입력받고 C에 A * B의 행렬 곱을 더해 결과를 저장한다

- 즉, C = A*B  가 아니라 C += A*B를 계산하는 것이다.

- 이때 C는 모든 원소가 0인 행렬이다. 

 

2.1. 행렬곱 구현

A = [[1,2],[3,4]]
B = [[5,6],[7,8]]
C = [[0,0],[0,0]]

for i in range(2):
    for j in range(2):
        for k in range(2):
            C[i][j] += A[i][k]*B[k][j]

C

------------------------------------------------------

[[19, 22], [43, 50]]

 

- 시간복잡도는 O(n^3)이다.

 

2.2. 분할 정복을 이용하여 행렬곱 구현

- 분할 정복을 이용하여 행렬곱을 구현하는 방법에 대해서 알아보자. 

- n > 1인 경우(n은 2의 거듭제곱), 분할 단계에서 n x n행렬을 네 개의 n/2 x n/2 부분 행렬로 나눈다. 

- n을 2의 거듭제곱이라고 가정한 이유는 재귀적으로 진행됨에 따라 부분 행렬의 차원이 정수가 되도록 하기 위함

 

 

- 해당 식을 알고리즘으로 변환할 때 구현하기 위한 일반적인 접근 방식은 크게 2가지가 존재한다.

 

1. 

- A의 네 개의 부분 행렬 A11, A12,A21,A22 | B의 네 개의 부분행렬 B11,B12,B21,B22를 저장할 리스트를 할당한 후,

- 각 요소를 적절한 부분 행렬의 위치에 복사한다.

- 그후, C의 네 개의 부분 행렬 C11, C12, C21,C22를 적절한 위치에 복사한다. 

- 분할 하는데 O(n^2)만큼 걸린다.

 

2.

- 인덱스 계산을 사용하는 것으로, 더 빠르고 실용적이다.

- 행렬을 분할하는 것 자체를 인덱스에 대한 산술 연산만 포함하며, 이는 행렬 크기와 무관하게 상수시간에 수행된다.

- 분할 하는데 O(1)만큼 걸린다. 

 

- 이를 코드로 구현해보자 (Divide 부분은 numpy로 간단하게 구현했지만 , 바닐라 파이썬을 이용하고 싶으면 인덱싱을 이용해도 좋다.)

import numpy as np

# 행렬을 재귀적으로 곱하는 함수
def matrix_multiply_recursive(A, B, C, n):
    if n == 1:
        # Base case: 행렬 크기가 1x1일 때
        C[0, 0] += A[0, 0] * B[0, 0]
        return
    
    # n/2 크기의 서브매트릭스 인덱스 계산
    mid = n // 2

    # 서브매트릭스 추출
    A11, A12, A21, A22 = A[:mid, :mid], A[:mid, mid:], A[mid:, :mid], A[mid:, mid:]
    B11, B12, B21, B22 = B[:mid, :mid], B[:mid, mid:], B[mid:, :mid], B[mid:, mid:]
    C11, C12, C21, C22 = C[:mid, :mid], C[:mid, mid:], C[mid:, :mid], C[mid:, mid:]

    # 재귀적으로 서브매트릭스 곱셈 실행
    matrix_multiply_recursive(A11, B11, C11, mid)
    matrix_multiply_recursive(A11, B12, C12, mid)
    matrix_multiply_recursive(A21, B11, C21, mid)
    matrix_multiply_recursive(A21, B12, C22, mid)
    matrix_multiply_recursive(A12, B21, C11, mid)
    matrix_multiply_recursive(A12, B22, C12, mid)
    matrix_multiply_recursive(A22, B21, C21, mid)
    matrix_multiply_recursive(A22, B22, C22, mid)

# 예시: 4x4 크기의 행렬 곱셈
n = 4
A = np.random.randint(0, 10, (n, n))  # 4x4 행렬 A
B = np.random.randint(0, 10, (n, n))  # 4x4 행렬 B
C = np.zeros((n, n), dtype=int)       # 결과 행렬 C

print("Matrix A:")
print(A)
print("\nMatrix B:")
print(B)

matrix_multiply_recursive(A, B, C, n)

print("\nMatrix C (Result of A * B):")
print(C)

--------------------------------------------------------------------------------
Output

Matrix A:
[[0 2 2 7]
 [2 9 6 1]
 [7 1 7 6]
 [3 7 3 5]]

Matrix B:
[[7 2 1 2]
 [6 0 5 2]
 [2 0 2 4]
 [6 1 1 3]]

Matrix C (Result of A * B):
[[ 58   7  21  33]
 [ 86   5  60  49]
 [105  20  32  62]
 [ 99  11  49  47]]