[Algorithm] 행렬의 곱셈(python)

❗ 본 포스팅은 Programmers의 코딩테스트 연습문제를 활용합니다. 다양한 문제를 풀어보고 싶다면

    Programmers를 방문하세요.

 

행렬의 곱셈이라는 문제이다.

이 문제를 풀기 위해서 우리는 행열의 연산을 알아야한다.

고등학교, 대학교때 배운 행렬의 곱셈을 떠올려보자.

 

 

행렬의 곱셈이 가능하려면 위의 그림처럼 행렬 A의 행 k와 행렬 B의 열 k가 같아야한다. 그래야 연산이 가능하다.

** 문제에서는 곱할 수 있는 행렬만 주어진다고 했으니 크게 고려할 사항은 아니다.

 

연산과정을 보면 a11*b11 + a12*b21 이 계산되어 하나의 원소가 만들어진다. 이런식으로 전부 계산하게 된다.

 

그렇다면 우리는 어떻게 문제를 풀어야 할까?

 

1. 연산되어 나오는 행렬의 사이즈(M*N)만큼 전부 0으로 초기화해준다.

    문제 예제1의 경우 [[0,0],[0,0],[0,0]]이 될 것이다.

 

2. 행렬의 모든 원소들을 하나하나 접근해서 곱하고 우리가 만든 배열의 위치에 맞게 더해준다.

    문제 예제1의 경우 아래와 같은 과정을 통해서 만들어지게됨.

코드를 보면 아래와 같다.

def solution(arr1, arr2):
    answer = [[0 for i in range(len(arr2[0]))] for j in range(len(arr1))] # 배열초기화

# 하나씩 접근하는 과정
    for i in range(len(arr1)):
        for j in range(len(arr2[0])):
            for z in range(len(arr1[0])):
                answer[i][j]+=(arr1[i][z]* arr2[z][j]) # 원소를 배열의 해당위치에 더해줌

    return answer