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

출처 : 프로그래머스 코딩테스트 연습, https://programmers.co.kr/learn/courses/30/lessons/12949

코딩테스트 연습 - 행렬의 곱셈

 

만만하게 봤는데 코드를 깔끔히 작성한다는 점에서 다른 사람들의 풀이를 공부해볼 가치가 있는 문제였다

 

 

풀이

 

def solution(arr1, arr2):
    answer = []
    for i in range(len(arr1)):
        arr = []
        for j in range(len(arr2[0])):
            count = 0
            for k in range(len(arr2)):
                count += arr1[i][k] * arr2[k][j]
            arr.append(count)
        answer.append(arr)
    return answer

 

---

 

시간 복잡도

 

-

 

다른 사람의 풀이를 보면서 알게 된 점

 

Asterisk(*)의 배열 Unpacking

 

* 기호로 배열을 Unpacking 할 수 있다.

 

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

print(*A) # 1 2 3
print(*B) # [4, 5, 6] [7, 8, 9]

 

받을 때도 배열로 받을 수 있다.

 

a, *b = [1, 2, 3, 4, 5]

#a = 1
#b = [2, 3, 4, 5]

 

이를 응용하면 input으로 받을 때도 배열로 받을 수 있다. 

 

 

zip 함수

 

a = [1, 2, 3]
b = [4, 5, 6]

for i, j in zip(a, b):
  print(i, j)
  
#1, 4
#2, 5
#3, 6

 

zip 함수는 iteratable한 객체를 받아 각 객체를 조합하여 iteratable한 객체를 return한다.

 

 

위를 응용한 전치 행렬 구하기

 

전치 행렬이란 행렬에 행렬의 행과 열을 바꾸는 연산을 가한 것을 의미한다.

 

B = [[1, 2, 3], [4, 5, 6]]

for B_col in zip(*B):
  print(B_col)
  
# (1, 4)
# (2, 5)
# (3, 6)

 

로직은 다음과 같다.

 

1. Asterisk로 배열을 분해하면 각 행이 list별로 분리됨.

2. 분리된 행들을 zip함수로 묶으면 열별로 묶여서 return

 

 

그리고 이를 이용한 풀이

 

def solution(arr1, arr2):
    answer = []
    for a in arr1:
        line = []
        for b in zip(*arr2):
            count = 0
            for index in range(len(a)):
                count += (a[index] * b[index])
                
            line.append(count)
                
        answer.append(line)
            
    return answer

 

이를 짧게 줄인 풀이

 

def solution(arr1, arr2):
    return [[sum(x*y for x, y in zip(a, b)) for b in zip(*arr2)] for a in arr1]

 

위를 떠올리며 하나씩 분석해보자.

 

1. for a in arr1              : a의 행들

2. for b in zip(*arr2)   : b의 열들

3. for x, y in zip(a, b)  : a의 행과 b의 열을 하나씩 묶은 tuple의 성분을 x, y로 칭함

4. sum(x*y)                    : 각 행과 열의 성분을 하나씩 곱한 것의 합

 

즉, a의 행과 b의 열을 가져와서 성분별로 차례로 하나씩 묶어 tuple를 만들고

이 성분들을 곱한 값을 더하여 이를 성분으로 하는 list를 만든다.

 

sum 함수는 for x, y에 연계되어있으므로 하나의 행과 열에 대해서 곱해진 값을 sum하고

이 곱해진 값이 for b in zip(*arr2)와 연계되어 있으므로 이를 각 열별로 반복하고

이를 리스트화 한것을 for a in arr1로 각 행 별로 반복한다.

 

 

고찰

 

생각보다 for로 구현할 때 k를 어떻게 작성해야하지로 고민했던 문제이다.

전치 행렬을 만들어서 하면 쉬울 것 같은데 이를 만드는데 시간이 더 걸릴 것 같아서 안했는데

zip함수와 Asterisk를 이용해서 쉽게 만들 수 있는 방법이 있었다...