[백준 알고리즘] - 행렬 곱셈 (2740번) with Python

📎 간략한 문제 정리

• 분할 정복의 문제로 두개의 행렬이 주어지고 행렬 곱셈의 결과를 출력하는 문제입니다.

📈 문제 분석

• 분할 정복으로 행렬 곱셈은 각 위치 요소의 곱의 합이기 때문에 요소들을 순회하며 곱과 합 연산을 반복하면 됩니다. 사실 분할 정복 문제라고 하기엔 행렬곱의 정의를 알고 있으면 그대로 구현하는 문제이므로 시뮬레이션 문제에 가깝습니다.

🙋‍♂️ 내가 처음 생각한 해결 방법

• 단순히 행렬곱의 정의대로 구현하면 되고, 포인트는 코드를 조금 더 간결하게 표현할 방법으로 잡았습니다.

💻 풀이한 코드

from sys import stdin
input = stdin.readline
AN, AM = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(AN)]
BN, BM = map(int, input().split())
B = [list(map(int, input().split())) for _ in range(BN)]
answer = [[0 for _ in range(BM)] for _ in range(AN)]
for i in range(AN):
    for j in range(BM):
        answer[i][j] = sum([A[i][k] * B[k][j] for k in range(AM)])
    print(" ".join(map(str, answer[i])))

📝 해결 과정에서 만난 문제, 고민들

• 사실 Numpy를 쓰면 한줄로 풀이 가능한 문제입니다. 하지만 Numpy는 외부 라이브러리 일반적인 코테에서 사용 불가능하므로 일일이 연산했습니다. 로직이 어렵지 않기 때문에 풀이 과정을 종이에 쓰고 매칭되는 요소들을 정리하며 반복문을 작성했습니다.

• 행렬 연산에는 조건이 필요합니다. 문제에는 명시되진 않지만(B의 행이 M이라는데에 들어있습니다.) 행렬곱 앞 요소의 열과 뒷 요소의 행의 개수가 같을 때에만 연산이 가능합니다. 로직에 그런 검증이 없으므로 생각할 요소가 적었습니다.

• 행렬을 입력받을 때 처음에는

  B = []
  for _ in range(BN):
      B.append(list(map(int, input().split())))

  처럼 빈 배열에 계속 요소를 입력하는 방식을 썼습니다. 사실 속도 차이는 거의 없겠지만 append 메소드가 느린 편이고 굳이 3줄로 작성해서 읽기 힘들게 만들 이유가 없기 때문에 아래와 같이 변경했습니다.

  B = [list(map(int, input().split())) for _ in range(BN)]

• 출력하는 print문을 처음에는 최종적으로 다시 순회하는 코드로 작성했었습니다.

  for i in range(len(answer)):
      print(" ".join(map(str, answer[i])))

  하지만 사실 그 바로 위에 answer의 요소를 갱신하는 순회 함수가 있고, 한 행이 완성되었을 때마다 출력해주어도 되기 때문에 print문을 아래와 같이 삽입했습니다.

  for i in range(AN):
      for j in range(BM):
          answer[i][j] = sum([A[i][k] * B[k][j] for k in range(AM)])
      print(" ".join(map(str, answer[i])))

  주의해야할 점은 print문이 어느 블럭에 존재하는지 입니다.

  big-O에는 영향이 없습니다. 속도 결정 구문이 아니기 때문입니다. 하지만 분명히 추가적인 순회가 발생하므로 속도에 차이는 발생할 수 있습니다. 그 속도 차이는 백준 제출 결과로 확인했습니다.

  

  코드 길이도 짧아졌고 시간도 짧아졌습니다. 하지만 메모리 사용은 더 커졌습니다. 빅오 표기법은 최악의 경우를 상정하기 때문에 빅오 표기법이 같아도 동작 속도는 분명히 달라질 수 있음을 기억할 필요가 있습니다.

https://www.acmicpc.net/problem/2740