23.02.27 파이썬 코딩 퀴즈#173 최적의 행렬 곱셈(프로그래머스 스쿨)

이번 문제는 최적의 행렬 곱셈 문제이다.

기본적으로 행렬의 곱셈 성립 조건의 A(m x n)의 열의 길이와 B(n x p)의 행의 길이가 같을 때에만 성립 가능하다.

그리고 연산 후 생성된 행렬 AB는 m x p 의 길이를 가진다.

그리고 새로운 행렬 C(p x l ) 과 연산하게 되면 최종적으로 행렬 ABC 는 m x l 의 길이를 가진다.

그리고 이대 연산의 횟수는 A x B = m x n x p 이며, AB x C = m x p x l 의 연산 횟수를 거치게 된다.

이를 수학적으로 더 표현하면 m x p x  (n + l) 이 된다.

 

위 예제를 통해 다시 설명을 되집어 보면

A (5 x 3), B(3 x 10) C (10 x 6) 이 있으며, 여기서 m, n , p , l 이 되는 값들은 각 5, 3, 10, 6 이다.

그리고 새롭게 만들어진 행렬 D 가 가능한 조합을 찾아보면, AB (5 x 10), BC(3 x 6 ) 두가지가 나온다.

따라서 5, 10 또는 3,6 이 m, p 가 되며 이때 값이 작은 3,6을 곱한다음 남은 5,10의 합을 곱한 270이 최소 연산 횟수가 된다.

 

한가지 문제는 전달받은 행렬의 개수는 3이상 200이하라는 것이다.

200개의 행렬의 곱셈을 시행하면서 최소 곱셈의 수를 찾아야 한다.

 

이 문제에서 생각해야할 부분은 총 2가지 이다.

1. 가장 연산 회수가 적은 행렬의 곱셈을 찾는 것!

2. 최종적으로 모든 행렬의 연산 곱셈이 가능한 방법을 찾는것.

 

다시 예를 들어서 [9, 10], [10, 9], [9, 1], [1, 2] 4개의 행렬을 계산한다고 가정해 보자. (편의상 A,B,C,D)

A = A*B[9*10*9], B*A[10*9*10]

B = B*C[10*9*1]

C = C*D[9*1*2]

각 행렬이 중복으로 들어가는걸 제외하면 4가지 행렬이 새로 만들어 진다.

 

그리고 다시 확인해 보면

AB([9,9] = AB*C [9*9*1]

BA[10,10] = X

BC[10,1] = A*BC[9*10*1], BC*D[10*1*2]

CD[9,2] = B*CD[10*9*2]

총 4개의 행렬이 만들어진다.

 

그리고 최종적으로 모든 행렬의 곱셈이 가능한 조합을 확인해보면

ABC[9,1] = ABC*D = [9*1*2]

ABC[9,1] = ABC*D = [9*1*2]

BCD[10,2] = A*BCD = [9*10*2]

총 3가지 값이 나오게 된다.

 

여기서 형태를 보면 최종적으로 ABCD 또는 BACD 형태이며, 이 때 계산한 순서에 따라

시작 AB(810) + AB*C(81) + ABC*D(18) = 909

시작 BC(90) + A*BC(90) + ABC*D(18) = 198

시작 BC(90) + BC*D(20) + A*BCD(180) = 290

시작 CD(18) + B*CD(180) + A*BCD(180) = 378

5가지 값이 나오게 되고, 최종적으로 198이 최소 연산 횟수가 된다.

 

위 연산에서 알 수 있듯이 연산이 가능한 배열이 주어졌을때 순서에 상관없이 서로 인접한 행렬끼리 계산만 진행하면 모든 행렬의 연산을 시행 할 수 있다. 즉 입접한 행렬만 확인해 주면 된다.

먼저 2차원 dp 배열을 만들어 주고, 값은 최대값(math.inf) 또는 임의의 큰 값으로 설정해 주고 시작한다.

그리고 같은 행렬끼리는 곱할 수 없기 때문에 (i,i) 위치는 모두 0으로 바꿔주고 시작한다.

i의 시작값은 1 이고, j의 시작값은 0 이다.그리고 끝나는 지점 end 의 값은 i+j 가 된다.

만약 end 값이 전체 배열의 길이를 벗어난 경우라면 연산이 불가하기에 break로 해당 j 에 대한 탐색을 종료하게 된다.

예를들어 i 가 1이고, j 가 2라면 end 는 3이 된다.

그리고 다시 k 는 (1.3 ) 범위를 반복하며 값을 가지며, 이때 dp[2][[3] 의 값을 찾게 된다.

여기서 m[k] 는 한번 연산된 행렬의 마지막 값이고, j 는 시작 행렬의 첫번째 값, m[end]는 마지막 행렬의 끝 값이다.

다시 말해 A(a*b), B(b*c), C(c*d), D(d*e)라고 가정하고 BC 를 기준으로 ABC를 계산한다고 가정하면

BC 는 b*d 배열이고 A*BC 는 a*b*d 이다. 이때 b의 위치를 연산된 행렬의 첫값으로 보고 계산하는 것이다.

행렬이 5개 이고, E(e*f)가 추가되었다면?

BCD 는 b*e 배열을 가지게 되고, BCD*E 라면 시작값은 B[0] 중간값은 D[1] 끝값은 E[1]디 된다.

 

구글링을 통해 해결하긴 했지만, 시작할 때 접근법은 좋았던 문제이다.

다만 코드로 구현하는데 생각보다 너무 오래 걸려서 구글링의 도움을 받았는데, 다음에는 좀 더 직관적인 코드를 작성해 봐야 할것 같다.