[프로그래머스] 행렬의 곱셈

문제

출처

이해

입력

• arr1, arr2
  • 타입: 배열
  • 길이: [2, 100]
  • 원소
    • 타입: 배열
    • 길이: [2, 100]
    • 원소
      • 타입: 정수
      • 범위: [-10, 20]

출력

• arr1에 arr2를 곱한 행렬

조건

1. 곱할 수 있는 행렬만 주어진다.
   • arr1의 열의 수가 arr2의 행의 수와 같다

예시

입출력

입력: 
arr1 = [[1, 4], [3, 2], [4, 1]]
arr2 = [[3, 3], [3, 3]]

출력: 
[[15, 15], [15, 15], [15, 15]]

접근

빠른 행렬 곱셉이 필요하다면 슈트라센의 알고리즘을 사용할 수 있으나, 입력을 살펴보면 최악의 경우 100 * 100 * 100 만큼의 곱셈이 필요하다는 것을 알 수 있다. 따라서 나이브한 구현으로도 통과할 수 있다. 행렬의 곱셈은 특별할 게 없지만 굳이 이 문제의 풀이를 작성하는 이유는 파이썬스러운 코드에 대해 생각해보기 위해서이다.

행렬 곱셈의 결과는 좌측 행렬의 row와 우측 행렬의 column에 대한 내적으로 나타낼 수 있다. C++을 사용하여 이 로직을 작성하게 되면 직접 index를 생각하며 작성해야 한다.

#include <vector>

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;

vvi solution(vvi arr1, vvi arr2) {
    vvi answer;
    answer.resize(arr1.size(), vi(arr2[0].size(), 0));
    for (int i = 0; i < arr1.size(); i++) {
        for (int j = 0; j < arr2[0].size(); j++) {
            for (int k = 0; k < arr2.size(); k++) {
                answer[i][j] += arr1[i][k] * arr2[k][j];
            }
        }
    }
    return answer;
}

이렇게 직접 index를 다루는 것은 그 의미를 한눈에 이해하기 어렵다. 심지어 다차원 배열이 낯선 사람은 이해하는 데에 시간이 걸릴 수도 있다. 하지만 python의 경우 index를 사용하지 않고 직관적인 코드를 작성할 수 있다.

def solution(A, B):
    answer = []
    for r in A:
        answer.append([])
        for c in zip(*B):
            answer[-1].append(sum([a * b for a, b in zip(r, c)]))
    return answer

for r in A = A의 행 r을 선택한다.
for c in zip(*B) = B의 열 c를 선택한다.
sum([a * b for a, b in zip(r, c)]) = r과 c의 내적을 구한다.

여기서 열을 선택하는 부분이 이해하기 어려울 수 있다. zip() 함수는 python의 내장함수인데 iterable한 객체”들”을 인자로 받고, 모든 객체의 원소에 함께 접근할 수 있게 해준다. 또한 *B의 *은 iterable한 객체인 B의 모든 원소를 밖으로 끄집어 내는 것을 의미한다. 이를 sequence unpacking이라고 부른다.

# 예를 들어 다음과 같은 함수가 있다고 해보자.
def sum(a, b):
    return a + b

# 이때 다음 두 식은 동일한 결과를 얻는다.
sum(1, 2)

li = [1, 2]
sum(*li)

이제 zip(*B) 는 우리가 원하는 B의 column과 정확히 동일한 의미가 된다는 것을 알 수 있다. 이렇게 추상적인 코드를 작성하면 index를 직접 조작하는 코드를 작성하는 것보다 실수할 확률을 줄일 수 있다. 짧고 의미가 분명할 수록 실수할 여지가 줄어들기 때문이다. 파이썬스러운 코드는 이렇게 코드의 의미를 잘 살린 코드라고 생각한다.

구현

# 앞에서 본 코드를 하나의 표현식으로 나타낼 수도 있다.
def solution(A, B):
    return [[sum([a * b for a, b in zip(r, c)]) 
                        for c in zip(*B)] 
                        for r in A]