알고리즘/알고리즘 개념
슈트라센 알고리즘
0. 행렬 곱셈 방법 아이패드 있을때 추가하기.. n * m 행렬과 m* k 행렬의 곱! 1. General Solution 1.1 브루트포스 # 일반적인 3중 반복문 행렬 곱셈 answer = [[0 for _ in range(k)] for _ in range(n)] for f in range(n): for s in range(k): for j in range(m): answer[f][s] += a[f][j] * b[j][s] 1️⃣ n번 반복하면서 첫번째 행렬의 행을 순회한다 2️⃣ k번 반복하면서 두번째 행렬의 열을 순회한다 3️⃣ m번 반복하면서 곱셈을 진행한다 ➡️ Θ(n^3)의 시간복잡도를 가진다 1.2 분할정복 8번의 곱셈이 필요하다 8번의 덧셈이 필요하다 ➡️ Θ(n^3)의 시간복잡도를 가..
