문제

https://programmers.co.kr/learn/courses/30/lessons/12949
2차원 행렬 arr1과 arr2를 입력받아, arr1에 arr2를 곱한 결과를 반환하는 함수, solution을 완성하시오.

---

권장 시간: 40분
권장 시간 복잡도: O(N^3)
출제: 연습문제

---

제약 조건

• 행렬 arr1, arr2의 행과 열의 길이는 2 이상 100 이하입니다.
• 행렬 arr1, arr2의 원소는 -10 이상 20 이하인 자연수입니다.
• 곱할 수 있는 배열만 주어집니다.

---

풀이

1. arr1, arr2의 행, 열 정보를 변수에 기록하고 행렬 정의를 활용해 결과 행렬을 저장할 수 있는 크기의 새 행렬을 만들어 0으로 초기화
2. 결과 행렬의 크기는 (r1, c2)이므로 해당 크기의 리스트를 미리 만들어 0으로 초기화
3. 행렬의 곱을 위한 반복문
4. 첫 번째 행렬의 i번째 행과 두 번째 행렬의 j번째 열을 곱함

def solution(arr1, arr2):
    # 행렬 arr1과 arr2의 행과 열 수
    r1, c1 = len(arr1), len(arr1[0])
    r2, c2 = len(arr2), len(arr2[0])
    
    # 결과를 저장할 2차원 리스트 초기화
    ret = [[0] * c2 for _ in range(r1)]
    
    # 첫 번째 행렬 arr1의 각 행과 두 번째 행렬 arr2의 각 열에 대해
    for i in range(r1):
        for j in range(c2):
            # 두 행렬의 데이터를 곱해 결과 리스트에 더해줌
            for k in range(c1):
                ret[i][j] += arr1[i][k] * arr2[k][j]
    return ret

---

시간 복잡도

• N은 행 또는 열의 길이
• 행과 열의 길이는 같음
  arr1의 행, 열을 r1, c1
  arr2의 행, 열을 r2, c2라 했을 때
  r1c1c2만큼 연산
• 최종 시간 복잡도는 O(N^3)