이즈미르의 프로그래밍

분할 정복 알고리즘(Divide and conquer algorithm) 중에 하나인 Strassen을 알아보자. 중고등학생 때 행렬의 곱셈에 대해 배웠을 것이다. 행렬 간에 곱셈을 하기 전에 곱셈이 가능한 행과 열로 행렬들이 갖춰졌는지 확인해야 하지만 우리는 정사각 행렬(Square matrix)만 다루기로 하자. 아래와 같이 각 크기가 n인 정사각 행렬 A, B가 있다고 하자. $$ A_{n,n} = \begin{bmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n} ..