[알고리즘] 행렬 연산

"""
    1. arr1의 n번째 한 행과 arr2의 m번째 한 열에 대해서 연산한다.
    2. 이때 한 행의 원소의 개수와 한 열의 원소의 개수는 동일하다.
    3. 한 행과 한 열의 각각의 원소끼리 내적 연산을 한다.
    4. 해당 연산의 값을 연산된 행렬의 n행 m열의 원소로 사용한다.
    5. 위와 같은 과정을 1 ~ n 행에 대해서 각각 1 ~ m 열에서 반복한다. 
    6. 최종적으로 O(n * m)의 시간 복잡도가 알고리즘의 시간 복잡도로 나온다.
    7. 입력되는 n과 m의 최댓값이 100이므로 위의 시간복잡도를 사용할 수 있다.

    arr2를 전치행렬로 만들고, 각각의 행에 내적연산을 시킨다.
    왜냐하면 곧이곧대로 구현을 하게 되면 n^3까지 시간 복잡도가 상승하게 된다.

    내적 연산의 시간 복잡도를 n^3 이하로 낮출 수 있는가?
"""

def solution(arr1, arr2):
    # arr2 전치행렬 연산
    new_arr2 = [ [0 for _ in range(len(arr2))] for _ in range(len(arr2[0]))]
    for i in range(len(arr2)):
        for j in range(len(arr2[0])):
            new_arr2[j][i] = arr2[i][j]

    # 내적 연산
    answer = [[0 for _ in range(len(new_arr2))] for _ in range(len(arr1))]
    for row in range(len(arr1)):
        for col in range(len(new_arr2)):
            value = 0
            for pair in zip(arr1[row], new_arr2[col]):
                value += pair[0] * pair[1]
            answer[row][col] = value

    return answer

놓친 점

행렬 연산은 아래의 코드로 간단하게 구현할 수 있다.
그런데 그것을 알지 못하고, 어렵게 구현해버렸다.

def solution(arr1, arr2):
	answer = [[0 for _ in range(len(arr2))] for _ in range(len(arr1))]
    for i in range(len(arr1)):
    	for j in range(len(arr2)):
        	for k in range(arr1[0]):
            	answer[i][j] = arr1[i][k] * arr2[k][j]