문제5 - 거리두기 확인하기 (Python)

프로그래머스

2차원 행렬 arr1과 arr2를 입력받아 두 행렬을 곱한 결과를 반환하는 문제입니다. 행렬의 곱셈은 단순히 원소끼리 곱하는 것이 아니라, 앞 행렬의 행과 뒤 행렬의 열을 순차적으로 내적(Dot Product)해야 하므로 정확한 인덱스 제어가 관건입니다.

---

1.  나의 풀이 (Modular Approach)

행렬의 크기를 먼저 결정하고, 3중 반복문을 통해 각 칸에 들어갈 합산 값을 계산했습니다.

def solution(arr1, arr2):
    row_len = len(arr1)
    col_len = len(arr2[0])
    answer = [[0] * col_len for _ in range(row_len)]

    for i in range(row_len):
        for j in range(col_len):
            sum_val = 0
            left = arr1[i]
            for m in range(len(left)):
                sum_val += arr2[m][j] * left[m]
            answer[i][j] = sum_val

    return answer

2.  오늘 배운 점 및 복기 노트

행렬 곱셈 "도미노 쓰러뜨리기" 암기법

행렬곱을 처음 한다면 행렬 곱셈의 흐름을 시각적으로 암기하면 좋습니다. 특히 "왼쪽에서 행을 하나씩 뽑아서 오른쪽 기둥에 세운다"는 이미지를 다음 3단계로

1. 먼저 곱셈이 가능한 형태인지 확인합니다. 앞 행렬이 $3 \times 2$이고 뒤 행렬이 $2 \times 2$처럼, 안쪽 숫자 2가 일치해야 서로 맞물리는 톱니바퀴처럼 연산이 가능합니다. 결과는 안쪽에 맞물린 부분을 제외한 바깥 숫자인 $3 \times 2$ 사이즈의 행렬이 나옵니다.
2. 앞 행렬의 가로줄(행)을 하나 뽑아서 오른쪽으로 7자를 그리며 쓰러지면서 뒤 행렬의 세로줄(열) 위로  상상합니다.

• 예시: 앞 행렬의 첫 줄 [1, 4]를 집어듭니다.
• 이를 시계 방향으로 90도 회전시켜 세웁니다.
• 그대로 뒤 행렬의 첫 번째 기둥 [3, 3] 옆에 붙입니다.
• 1은 위쪽 3과, 4는 아래쪽 3과 만나며 $(1 \times 3) + (4 \times 3) = 15$가 도출됩니다.

결과 확인

제시된 예시에서는 어떤 행을 가져와도 기둥의 숫자가 모두 3이므로 다음과 같은 결과가 나옵니다.

• 1행 계산: [1, 4]와 [3, 3] $\rightarrow 3 + 12 = 15$
• 2행 계산: [3, 2]와 [3, 3] $\rightarrow 9 + 6 = 15$
• 3행 계산: [4, 1]와 [3, 3] $\rightarrow 12 + 3 = 15$

최종 결과 행렬은 다음과 같습니다.

$$\begin{bmatrix} 15 & 15 \\ 15 & 15 \\ 15 & 15 \end{bmatrix}$$

 

 

---

3. 프로그래머스 코딩 테스트 문제 풀이 전략 교재에서 배울만한 점

시간 복잡도 $O(N^3)$의 필연성

3중 반복문을 사용하는 구조상 행렬 곱셈의 시간 복잡도는 $O(N^3)$이 됩니다. 제한 조건인 행렬 크기 100을 대입하면 $1,000,000$번의 연산이 발생하며, 이는 코딩 테스트의 시간 제한 내에 충분히 수행 가능한 범위임을 인지해야 합니다.

 

인덱스 $k$를 통한 표준 수식 이해

교재에서 강조하는 $arr1[i][k] \times arr2[k][j]$ 수식에서 $k$는 양쪽 행렬을 잇는 공통 인덱스로 사용했습니다.

제 코드에서는 left = arr1[i]를 통해 한 줄을 미리 참조하는 변수를 만들어  $k$ 인덱스의 접근을 최적화하고 가독성을 높였습니다.