문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/12949
문제설명
2차원 행렬 arr1과 arr2를 입력받아, arr1에 arr2를 곱한 결과를 반환하는 함수, solution을 완성해주세요.
제한 조건
- 행렬 arr1, arr2의 행과 열의 길이는 2 이상 100 이하입니다.
- 행렬 arr1, arr2의 원소는 -10 이상 20 이하인 자연수입니다.
- 곱할 수 있는 배열만 주어집니다.
입출력 예
문제 이해
겉으로 보기에는 간단한, 행렬곱을 코딩하는 문제이다.
행렬 곱을 표현하면 다음과 같다.
- (m, k)의 A 행렬과 (k, n)의 B 행렬을 곱했을 때
- A행렬의 i행과 B행렬의 j열의 성분을 각각 곱하고,
- 이를 모두 더한 값이 AxB 행렬의 (i, j)번째 성분이 된다.
따라서 이를 코드로 나타내면 다음과 같다.
문제풀이
1. 직관적으로 푸는 방법
def solution(arr1, arr2):
answer = []
for i in range(len(arr1)): # i번쨰 행의 k번째 성분과
row = []
for j in range(len(arr2[0])): # j번째 열의 k번째 성분을 곱한다.
dot = 0
for k in range(len(arr2)):
dot += arr1[i][k] * arr2[k][j] # 이를 각각 곱해서, 더하면
row.append(dot) # 새로운 행렬의 (j) 번째 칸에 넣어준다.
answer.append(row) # 한 줄이 만들어 질때마다 넣어준다.
return answer
시간복잡도: O(N^3)
- 총 세개의 for문을 돌리므로
- O(len(arr2) * len(arr2[0]) * len(arr1)) 만큼 시간이 소요된다.
- 이 때, arr1, arr2모두 (N,N)행렬이라고 가정하면, O(N^3)이 된다.
공간복잡도: O(len(arr1) * len(arr2[0])
- 눈치빠른 사람은 알겠지만, 최종적으로 만들어지는 행렬의 크기(m,n)만큼 공간을 차지한다.
이 풀이를 좀 더 직관적으로 표현해보자.
'''
조금 더 직관적으로 표현.
arr1의 shape를 (m, k)
arr2의 shape를 (k, n)
이라고 하면
'''
def solution(arr1, arr2):
n = len(arr2[0]) # arr2의 열 갯수 n
m = len(arr1) # arr1의 행 갯수 m
answer = [[0]*n for _ in range(m)] # (i,j) 형태의 matrix를 만들어 줍니다.
for i in range(len(arr1)): # i번쨰 행의 k번째 성분과
row = []
for j in range(len(arr2[0])): # j번째 열의 k번째 성분을 곱한다.
dot = 0
for k in range(len(arr2)):
dot += arr1[i][k] * arr2[k][j] # 이를 각각 곱해서, 더하고
answer[i][j] = dot # 새로운 행렬의 (i,j) 번째 칸에 넣어준다.
return answer
2. 한줄에 다 넣어서 푸는 방법
def productMatrix(A, B):
return [[sum(a*b for a, b in zip(A_row,B_col)) for B_col in zip(*B)] for A_row in A]
시간복잡도: O(N^3)
공간복잡도: O(N^2)
풀이가 간단하면서도 신박했다. 하지만, 간단한만큼 직관적이지는 않았다.
하나씩 살펴보자.
1.
[[...] for A_row in A]
1. A행렬에서 한줄씩 읽어온다.
2.
[[sum(...) for B_col in zip(*B)] for A_row in A]
2. B 행렬에서 각 column을 받아온다.
부가 설명>
B matrix에서 asterisk(*)을 넣으면, 쉽게 말하자면 겉 껍데기를 벗겨내는 것과 같다.
예를 들어,
이렇게 생겼을 경우,
- a = [[10,20], [30,40], [50, 60]]
- *a = [10,20], [30,40], [50, 60]
가 된다. 여기서 zip을 하게 되면, *a에서 각 원소끼리 다시 묶여서 리스트를 형성한다.
즉,
- zip(*a) = [10, 30, 50], [20, 40, 60]
이 된다.
이 부분이 특이했고, 파이썬에 대해서 하나의 트릭을 발견한 것 같다.
3.
[[sum(a*b for a, b in zip(A_row,B_col)) for B_col in zip(*B)] for A_row in A]
3. 이렇게 해서 얻은 A_row와 B_col에서
- 각각 요소 a, b를 뽑아내서 곱한 후,
- sum()을 통해서 더하면,
- i,j의 요소가 된다.
리뷰
- 문제 내용 자체는 쉬운데, for문으로 어떻게 행렬곱을 풀이할지에 대한 것이 관건이었다.
머릿속으로만 계산하려니 헷갈려서 종이로 직접 풀어 봤더니 풀렸다.
그리고, 처음에는 설명하기 애매했는데, 포스팅을 하면서 조금씩 설명할 수 있게 되었다.
하나씩 하나씩 풀면서 풀이를 설명하는 것 또한 연습해보자.
그리고, 남들이 푼 코드를 보면서 zip()에 대한 새로운 시각도 열린 것 같아 좋았다.
'정리 > 알고리즘' 카테고리의 다른 글
[프로그래머스] 입국심사 (0) | 2023.10.08 |
---|---|
[프로그래머스] N개의 최소공배수 (0) | 2023.04.30 |
[프로그래머스]하노이의탑 (0) | 2023.04.17 |
코테 포스팅의 시작 (0) | 2023.04.17 |