Matrix Chain Multiplication
행렬의 연쇄는 dims로 설명됩니다. 행렬 i의 행 개수는 dims[i]이고 열 개수는 dims[i+1]이므로, 각 행렬은 다음 행렬과 곱할 수 있습니다. p × q 행렬에 q × r 행렬을 곱하는 데는 스칼라 곱셈이 p × q × r회 필요하며, 결과는 p × r 행렬입니다. 괄호를 배치하는 모든 방법은 최종 곱은 같지만 비용은 같지 않습니다. 전체 연쇄를 곱하는 데 필요한 스칼라 곱셈의 최소 횟수를 반환하세요.
함수
- dimsinteger-array
- 연쇄를 따라 각 크기는 다음과 같습니다. 행렬 i의 크기는 dims[i] × dims[i+1]입니다.
- 반환값integer
- 전체 체인을 곱하는 데 필요한 스칼라 곱셈의 최소 횟수
제약 조건
2 ≤ dims.length ≤ 100이므로, 이 체인에는 행렬이 1개에서 99개까지 포함됩니다.1 ≤ dims[i] ≤ 100- 정답은 최대 98 × 106으로, 32비트 부호 있는 정수 범위에 충분히 들어갑니다.
예제
- 입력
- dims = [4, 10, 3, 12]
- 출력
- 264
- 설명
- 처음 두 행렬을 곱하는 데 4 × 10 × 3 = 120이 들고 4 × 3 행렬이 남습니다. 여기에 3 × 12 행렬을 곱하면 144가 더해져 총 264입니다. 다른 순서로 계산하면 360 + 480 = 840이 듭니다.
- 입력
- dims = [6, 2, 7, 3, 5]
- 출력
- 132
- 설명
- 2 × 7에 7 × 3을 곱하고(42), 2 × 3의 결과에 3 × 5를 곱한 다음(30), 6 × 2에 2 × 5의 결과를 곱합니다(60). 합계는 132입니다.
- 입력
- dims = [3, 7]
- 출력
- 0
- 설명
- 행렬은 3 × 7 하나뿐이므로 곱셈이 이루어지지 않으며 비용은 0입니다.
후속 질문
최소 비용을 만드는 서로 다른 괄호화 방식이 몇 개인지도 셀 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
첫 번째 곱셈은 잊고 마지막 곱셈에 대해 생각해 보세요. 어떤 순서를 선택하든, 마지막 단계에서는 체인의 왼쪽 부분의 곱과 나머지 부분의 곱을 곱합니다.
두 경계
left와right사이 행렬들의 곱은 항상dims[left] × dims[right]행렬입니다. 따라서 마지막 단계에서 경계split을 기준으로 해당 구간을 나누면 비용은dims[left] × dims[split] × dims[right]이고, 두 부분은 같은 문제의 더 작은 복사본입니다.경계
left와right사이의 행렬을 곱하는 가장 저렴한 방법을best[left][right]에 저장합니다(행렬 하나인 경우 0). 이는 두 경계 사이에 엄격히 놓인 모든split에 대해best[left][split] + best[split][right] + dims[left] × dims[split] × dims[right]중 최솟값입니다. 좁은 구간을 넓은 구간보다 먼저 계산합니다.
풀이
순서에 따라 비용이 달라집니다. 첫 번째 예에서는 264와 840입니다. 마지막 곱셈을 살펴보세요. 체인의 왼쪽 부분과 오른쪽 부분의 곱을 결합하며, 각 부분은 더 짧은 체인에서 같은 문제입니다. 체인의 구간을 대상으로 한 표를 사용하면 각 문제를 한 번씩, O(n³) 시간에 해결할 수 있습니다.
일반 재귀로 모든 분할을 시도합니다
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
체인의 경계에 0부터 m-1까지 번호를 매깁니다. 여기서 m = dims.length입니다. 경계 k의 크기는 dims[k]입니다. 경계 left와 right 사이의 행렬들은 어떤 순서로 곱해도 dims[left] × dims[right] 행렬이 됩니다. 따라서 마지막 단계에서 해당 구간을 split에서 나눈다면, 두 블록 내부에서 어떤 연산이 이루어졌든 그 단계의 비용은 dims[left] × dims[split] × dims[right]입니다. 각 블록은 가능한 한 적은 비용으로 만들어야 하므로, cheapest(left, right)는 모든 split을 고려해 두 블록의 비용과 마지막 단계의 비용을 더한 값 중 최솟값입니다. 가능한 모든 마지막 단계를 시도하면 올바른 결과를 얻을 수 있습니다.
같은 구간을 계속해서 다시 계산합니다. 행렬이 n개라면 호출 횟수는 3^(n-1)회이며, 행렬이 20개일 때 약 1.2 × 10^9회입니다. 하지만 서로 다른 구간은 약 m²/2개뿐입니다.
알고리즘
- 경계
left와right사이의 행렬에 대해cheapest(left, right)를 작성하세요. right - left < 2이면 행렬이 하나이므로 0을 반환하세요.- 두 경계 사이에 있는 모든
split에 대해cheapest(left, split),cheapest(split, right)및dims[left] × dims[split] × dims[right]를 더하세요. - 가장 작은 합을 반환하세요.
- 정답은
cheapest(0, m-1)입니다.
def matrixChainOrder(dims):
def cheapest(left, right):
# The fewest multiplications for the matrices between boundaries left and right
if right - left < 2:
return 0 # a single matrix costs nothing
best = None
for split in range(left + 1, right):
cost = (cheapest(left, split) + cheapest(split, right)
+ dims[left] * dims[split] * dims[right])
if best is None or cost < best:
best = cost
return best
return cheapest(0, len(dims) - 1)메모를 사용한 재귀
핵심 아이디어
호출은 left와 right에만 의존합니다. 결과를 memo[left][right]에 저장하세요. 모든 셀은 실제 비용이 될 수 없는 값인 -1로 시작하며, 이후 호출에서는 재귀하는 대신 해당 셀의 값을 읽습니다. 약 m²/2개의 각 쌍은 m보다 적은 분할 횟수로 한 번씩만 해결됩니다. 즉, O(n³)이며 행렬 99개에서는 분할 확인이 161,700회입니다. 재귀 깊이는 체인 길이를 넘지 않으므로, 호출 스택 어디서든 경계 100개를 처리할 수 있습니다.
알고리즘
m개의 행과m개의 열이 있고 모든 셀이 -1인memo를 할당합니다.cheapest(left, right)에서 행렬이 하나만 있는 구간은 0을 반환하고, -1이 아닌 셀은 저장된 비용을 반환합니다.- 그렇지 않으면 단순 재귀와 정확히 같은 방식으로 모든
split의 비용을 계산하고 최솟값을 구합니다. - 반환하기 전에 그 최솟값을
memo[left][right]에 씁니다. - 정답은
cheapest(0, m-1)입니다.
def matrixChainOrder(dims):
m = len(dims)
# memo[left][right]: the answer for boundaries left and right, -1 while unknown
memo = [[-1] * m for _ in range(m)]
def cheapest(left, right):
if right - left < 2:
return 0 # a single matrix costs nothing
if memo[left][right] != -1:
return memo[left][right]
best = None
for split in range(left + 1, right):
cost = (cheapest(left, split) + cheapest(split, right)
+ dims[left] * dims[split] * dims[right])
if best is None or cost < best:
best = cost
memo[left][right] = best
return best
return cheapest(0, m - 1)늘리기 너비로 표 채우기
핵심 아이디어
각 셀은 더 좁은 구간에만 의존하므로, 루프를 사용해 좁은 구간부터 넓은 구간까지 best[left][right]를 채울 수 있습니다. 너비가 1이면 행렬 하나뿐이며 값은 0으로 유지됩니다. 더 넓은 구간에 도달하면 모든 분할에서 두 부분이 이미 계산되어 있습니다. dims = [6, 2, 7, 3, 5]일 때:
- 너비 2:
best[0][2] = 84,best[1][3] = 42,best[2][4] = 105. - 너비 3:
best[0][3]은 78입니다(분할 1: 0 + 42 + 36).best[1][4]는 72입니다(분할 3: 42 + 0 + 30). - 너비 4: 분할 1, 2, 3의 결과는 각각 0 + 72 + 60 = 132, 84 + 105 + 210 = 399, 78 + 0 + 90 = 168이므로,
best[0][4] = 132입니다.
최상위 분할이 경계 1에서 이루어진다는 것은 두 번째 예시처럼 6 × 2 행렬이 마지막에 결합된다는 뜻입니다. 시간과 메모리 사용량은 메모이제이션 버전과 같으며, 재귀는 사용하지 않습니다.
알고리즘
m = dims.length라고 두고, 0으로 초기화된m × m테이블best를 할당합니다.width를 2부터m-1까지 반복합니다. 그 안에서right = left + width가 여전히 경계 안에 있는 동안left를 0부터 증가시키며 반복합니다.- 해당 구간에서
left+1부터right-1까지 모든split에 대해best[left][split] + best[split][right] + dims[left] × dims[split] × dims[right]를 계산하고, 최솟값을best[left][right]에 저장합니다. - 정답은
best[0][m-1]에 있습니다.
def matrixChainOrder(dims):
m = len(dims)
# best[left][right]: the fewest multiplications for the matrices
# between boundary left and boundary right (0 for a single matrix)
best = [[0] * m for _ in range(m)]
for width in range(2, m):
for left in range(m - width):
right = left + width
low = None
for split in range(left + 1, right):
# the last product joins a dims[left] x dims[split] block
# with a dims[split] x dims[right] block
cost = best[left][split] + best[split][right] + dims[left] * dims[split] * dims[right]
if low is None or cost < low:
low = cost
best[left][right] = low
return best[0][m - 1]
함정과 경계 사례
- 가장 저렴한 쌍을 먼저 곱하기.
[10, 10, 1, 9]에서는 마지막 쌍의 비용이 가장 낮지만(90), 그다음 단계의 비용은 900이므로 총 990입니다. 첫 번째 쌍을 먼저 곱하면 비용은 190입니다. - 잘못된 셀에서 답을 읽기. 행렬 개수보다
dims의 항목이 하나 더 많으므로 답은best[0][m-1]이지best[0][m]이 아닙니다. - 바깥쪽 루프에서
left를 오름차순으로 순회하기. 그러면 행left에서 아직 0인 뒷 행의best[split][right]를 읽게 됩니다. 너비를 바깥쪽 루프에 두거나left를 내림차순으로 세세요. - 행렬이 하나인 경우를 빠뜨리기.
[3, 7]은 0을 반환해야 합니다. R에서는 루프2:(m-1)이2:1이 되어 역방향으로 실행되므로, 이를 방지하는 조건을 넣으세요.
자주 묻는 질문3
행렬 연쇄 곱셈의 시간 복잡도는 얼마인가요?
표에는 약 n²/2개의 구간이 있고 각 구간에서 최대 n개의 분할점을 시도하므로, 동적 프로그래밍은 O(n³) 시간과 O(n²) 메모리를 사용합니다. 메모이제이션을 사용하지 않는 단순 재귀는 행렬이 n개일 때 3^(n-1)번 호출합니다.
행렬 곱셈의 순서가 중요한 이유는 무엇인가요?
행렬 곱셈은 결합법칙이 성립하므로 (AB)C와 A(BC)는 같은 행렬을 만들지만, 중간 행렬의 크기는 다릅니다. 첫 번째 예에서 (AB)C는 4 × 3 행렬을 만들며 비용은 264인 반면, A(BC)는 10 × 12 행렬을 만들며 비용은 840입니다.
최적의 괄호 묶기 자체는 어떻게 찾나요?
승리한 분할을 best[left][right] 옆의 choice[left][right]에 저장합니다. 출력할 때 행렬 하나는 이름을 출력하고, 더 긴 구간은 여는 괄호, choice[left][right]까지의 부분, 그 뒤의 부분, 닫는 괄호를 출력합니다. 이렇게 하면 O(n²)의 메모리가 추가됩니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def matrixChainOrder(dims):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자
dims = [4, 10, 3, 12]
예상 출력
264