[ 백준 ] 18236 행렬 곱셈 순서 2 ( Python )
안녕하세요, 여러분! 오늘은 백준 온라인 저지에 있는 “행렬 곱셈 순서 2” 문제에 대해 알아보도록 하겠습니다. 이 문제는 동적 계획법(DP)의 고급 문제 중 하나인데요, 특별히 Hu-Shing 알고리즘을 활용하여 효율적으로 해결할 수 있습니다.
문제 자체는 간단합니다. 행렬의 개수 N과 각 행렬의 크기가 주어졌을 때, 모든 행렬을 곱하는데 필요한 곱셈 연산의 최소 횟수를 구하는 것이 목표입니다. 단, 입력으로 주어진 행렬의 순서는 바꿀 수 없습니다.
처음에 이 문제를 접했을 때, 가장 먼저 떠오른 아이디어는 동적 계획법을 사용하는 것이었습니다. 그러나 단순한 동적 계획법으로는 시간 복잡도가 O(n^3)으로 매우 높아, 문제의 제한 시간 내에 해결할 수 없었습니다.
3 Days Later….
3일동안 이를 갈고 고민하던 중 Hu-Shing 알고리즘이라는 효율적인 알고리즘을 알게 되었습니다. Hu-Shing 알고리즘은 행렬 곱셈 순서 최적화 문제를 O(nlogn) 시간 복잡도로 해결할 수 있는 강력한 알고리즘입니다.
여기에선 Hu-Shing 알고리즘 논문 을 요약하여 설명하겠습니다.
Hu-Shing 논문보기
우선 행렬 곱셈 순서 최적화 문제를 볼록 다각형 분할 문제로 변환하는 과정을 자세히 살펴보겠습니다. $n$개의 행렬 $M_1, M_2, \ldots, M_n$이 주어졌을 때, $M_i$는 $r_{i-1} \times r_i$ 크기의 행렬입니다. 이들을 곱하는 순서에 따라 연산량이 달라지게 되는데, 최적의 곱셈 순서를 찾는 것이 목표입니다.
저자들은 이를 위해 각 행렬을 하나의 변으로 갖는 볼록 다각형을 생각합니다. 예를 들어 행렬이 3개라면 삼각형, 4개라면 사각형이 대응됩니다. 이 때 꼭지점 $i$에는 $r_i$라는 가중치가 부여되며, 다각형의 변은 행렬의 크기 정보를 담고 있게 됩니다.
이제 원래 문제는 이 다각형을 대각선으로 적절히 분할하는 문제로 바뀌게 됩니다. 분할된 하나의 삼각형은 두 행렬의 곱을 의미하며, 삼각형의 cost는 두 행렬을 곱할 때 필요한 연산량에 해당합니다. 전체 분할의 cost, 즉 모든 삼각형의 cost 합은 행렬 곱셈에 필요한 총 연산량과 같아집니다. 따라서 분할의 cost를 최소화하는 것이 곧 최적의 행렬 곱셈 순서를 찾는 것과 동치가 됩니다.
이 변환의 정당성은 귀납법을 통해 증명됩니다 (보조정리 1). 우선 행렬이 2개일 때 성립함은 자명합니다. 행렬 2개의 곱은 삼각형 하나로 표현되고, 곱셈 연산량과 삼각형의 cost가 정확히 일치합니다.
이제 $k$개의 행렬에 대해 변환이 성립한다고 가정하고 $k+1$개의 행렬에 대해 생각해봅시다. $k+1$개의 행렬을 최적으로 곱하는 순서는 항상 어떤 위치 $p$ $(1 \leq p \leq k)$에서 두 부분으로 나눌 수 있을 것입니다. 즉, 앞의 $p$개 행렬의 곱과 뒤의 $k+1-p$개 행렬의 곱을 계산한 뒤 이 둘을 곱하는 꼴이 되어야 최적이 될 수 있습니다:
\[M = (M_1 \times M_2 \times \cdots \times M_p) \times (M_{p+1} \times \cdots \times M_{k+1})\]이는 볼록 다각형으로도 동일하게 해석할 수 있습니다. $V_1$-$V_2$-$\ldots$-$V_p$로 이어지는 $p$각형과 $V_p$-$\ldots$-$V_{k+1}$로 이어지는 $(k-p+2)$각형은 각각 최적 분할 상태에 있을 것이고, 최종적으로는 $V_1$과 $V_p$를 연결하는 대각선으로 전체를 두 부분으로 나눌 때 최적이 될 것입니다.
$V_1$-$V_p$를 연결하는 대각선, 즉 가장 마지막에 곱해지는 삼각형의 cost는 다음과 같이 계산됩니다:
- $p$각형의 최적 분할 cost ($= C(w_1, w_2, \ldots, w_p)$): 앞 $p$개 행렬의 최적 곱셈 연산량
- $(k-p+2)$각형의 최적 분할 cost ($= C(w_p, \ldots, w_k, w_{k+1})$): 뒤 $k+1-p$개 행렬의 최적 곱셈 연산량
- 1차원 벡터 $r_0 \times r_p$와 $r_p \times r_k$로 이루어진 두 행렬의 곱셈 연산량: $w_1 w_p w_{k+1}$
따라서 전체 $(k+1)$각형의 최적 분할 cost는 $k+1$개 행렬의 최적 곱셈 연산량과 정확히 일치하게 되어 귀납 증명이 완료됩니다:
\[C(w_1, w_2, \ldots, w_{k+1}) = C(w_1, w_2, \ldots, w_p) + C(w_p, \ldots, w_k, w_{k+1}) + w_1 w_p w_{k+1}\]이 변환을 통해 우리는 이제 행렬 대신 볼록 다각형만 생각하면 됩니다. 볼록 다각형을 ‘어떻게 삼각형으로 분할할 때 cost의 합이 최소가 되는가’라는 형태로 문제가 바뀐 것입니다. 저자들은 이를 ‘볼록 다각형 최적 분할 문제 (Optimum Convex Polygon Partitioning Problem)’이라 명명하고, 이에 대한 최적해의 특성을 규명하고자 합니다.
첫째로 증명하는 것은 임의의 최적분할은 항상 적어도 두 개의 이등변 삼각형 (한 변을 공유하는 삼각형 쌍)을 포함한다는 것입니다 (정리 1). 이를 위해 모든 꼭지점의 차수, 즉 꼭지점에 연결된 변과 대각선의 수를 분석합니다.
볼록 $n$각형은 $n$개의 변과 $n-3$개의 대각선으로 분할됩니다. 따라서 꼭지점의 차수 합은 $2n + 2(n-3) = 4n-6$이 되어야 합니다. 만약 이등변 삼각형이 없다고 가정하면, 분할에 참여하는 모든 삼각형은 세 꼭지점의 차수가 3 이상이어야 합니다. 이는 $n-2$개의 삼각형에 $3(n-2)$개 이상의 차수가 필요하다는 뜻인데, 이는 앞서 계산한 전체 차수의 합 $4n-6$과 모순됩니다 ($n > 3$일 때 $3(n-2) > 4n-6$). 따라서 임의의 최적분할은 반드시 한 변을 공유하는, 즉 차수가 2인 꼭지점을 갖는 삼각형 쌍을 포함해야만 합니다.
다음으로 저자들은 꼭지점들을 크기 순서대로 $V_1, V_2, \ldots, V_n$이라 명명하고, 볼록 $n$각형의 최적분할은 항상 $V_1$-$V_2$와 $V_1$-$V_3$의 변 (또는 대각선)을 포함함을 증명합니다 (정리 2). 이는 정리 1에서처럼 이등변 삼각형의 존재성을 보장하는 결과입니다. 즉, 가장 작은 꼭지점 $V_1$을 기준으로 그 다음으로 작은 $V_2$와 $V_3$가 반드시 연결되어야 한다는 의미입니다.
증명은 귀납법으로 이뤄집니다. 우선 $V_2$ 또는 $V_3$가 이등변 삼각형을 이루는 경우라면 당연히 $V_1$-$V_2$ 또는 $V_1$-$V_3$가 최적분할에 포함되어야 합니다. 이때 $V_1$이 아닌 다른 꼭지점이 차수 2를 갖는다면, 해당 꼭지점을 분리해 내어도 $V_1$-$V_2$ 또는 $V_1$-$V_3$ 연결이 보존됨을 쉽게 보일 수 있습니다 (귀납 가정).
한편 $V_1$과 $V_2$ (또는 $V_3$) 둘 다 차수 2를 갖는 경우라면, $V_1$-$V_2$ (또는 $V_1$-$V_3$) 대신 다른 대각선을 연결하는 것은 최적성을 해친다는 사실을 증명할 수 있습니다. 대각선을 연결하되 비용은 그대로 유지하려면 꼭지점 가중치가 같아야 하는데, 이는 $V_1$이 최소 가중치를 갖는다는 조건에 모순되기 때문입니다. 따라서 $V_1$-$V_2$와 $V_1$-$V_3$는 반드시 최적분할에 포함되어야 합니다.
위의 결과들을 바탕으로, 저자들은 특별한 형태의 최적분할인 ‘fan’과 ‘monotone polygon’에 대해 살펴봅니다. Fan은 한 꼭지점에서 다른 모든 꼭지점으로 연결된 대각선 집합을 말하며, monotone polygon은 꼭지점 가중치가 단조 증가하다가 단조 감소하는 볼록 다각형입니다. 이들은 이후 O($n \log n$) 알고리즘을 설계하는 데 핵심적인 역할을 합니다.
이제 Part II로 넘어가 Hu-Shing 알고리즘의 실제 동작 과정을 자세히 살펴보겠습니다. 알고리즘의 주요 아이디어는 다음과 같습니다:
- 주어진 볼록 다각형에 대해 모든 ‘후보 h-arc’를 찾는다 (h-arc의 정의는 뒤에서 다룸).
- 각 h-arc에 대해 그 arc를 포함하는 부분다각형의 최적분할을 구한다.
- 부분다각형을 h-arc로 둘로 나누고, 각 부분에 대해 재귀적으로 최적분할을 구한다.
- 이 때 두 부분다각형에 대한 최적해를 합치면 원래 부분다각형의 최적해가 된다.
- 전체 다각형의 최적해는 루트 h-arc에 대한 부분다각형의 최적해와 같다.
여기서 h-arc (horizontal arc)란, $V_a$-$V_b$-$V_c$-$V_d$ 순서의 꼭지점에 대해 다음 조건을 만족하는 대각선 $V_a$-$V_c$를 말합니다 (정리 3):
\[\frac{1}{w_a} + \frac{1}{w_d} \leq \frac{1}{w_b} + \frac{1}{w_c}\]이러한 h-arc들은 서로 교차하지 않으며, 최적분할에 포함될 가능성이 높은 대각선들입니다. 따라서 h-arc들만 고려하면 탐색 범위를 크게 줄일 수 있습니다.
알고리즘의 첫 단계에서는 one-sweep 방법으로 모든 h-arc를 추출합니다. 볼록 다각형의 꼭지점을 시계방향으로 한 바퀴 순회하면서, 스택을 이용해 h- arc 조건을 만족하는 대각선을 찾아내는 것입니다. 이 과정에서 중요한 것은 현재 처리 중인 꼭지점과 스택에 저장된 마지막 두 꼭지점만 보면 된다는 점입니다. 새로운 꼭지점을 스택에 추가하되, 추가 직전에 h-arc 조건을 검사하여 필요한 대각선만 골라내는 방식으로 동작합니다. 이렇게 하면 O($n$)에 모든 h-arc를 구할 수 있습니다.
다음으로, 추출된 h-arc들 간의 포함관계를 분석하여 트리 구조로 정리합니다. 이를 arc-tree라 부르는데, 루트는 전체 다각형에 대응되고 리프는 각각의 h-arc에 대응됩니다. 즉, arc-tree의 각 노드는 h-arc 하나와 그에 의해 둘로 나뉘는 부분다각형을 표현하게 됩니다. 이 트리의 구축에는 각 h-arc의 꼭지점 번호 범위를 비교하는 과정이 필요하므로 O($n \log n$)이 소요됩니다.
이제 arc-tree의 리프에서 루트로 향하는 후위순회(post-order traversal) 과정을 통해, 각 h-arc에 대한 부분다각형의 최적해를 bottom-up 방식으로 구해나갑니다. 한 h-arc $V_a$-$V_c$에 대응되는 부분다각형은 $V_a$와 $V_c$ 사이의 꼭지점들로 이루어집니다. 이 부분다각형을 $V_a$-$V_c$로 둘로 나누고, 각 부분에 대해 재귀적으로 최적분할 비용을 계산합니다. 그리고 그 합이 바로 현재 부분다각형의 최적분할 비용이 됩니다.
여기서 주목할 점은, 한 h-arc의 부분다각형에 대한 최적분할을 구할 때 그 안에 포함된 h-arc들에 대한 계산 결과를 활용할 수 있다는 것입니다. 포함관계가 arc-tree에 그대로 반영되어 있기 때문에, 트리를 따라 리프에서 루트로 거슬러 올라가는 동안 답을 효율적으로 합쳐나갈 수 있습니다. 이것이 동적계획법(dynamic programming)의 핵심 아이디어입니다.
각 h-arc 단위의 DP 계산에서 유의할 점은, 해당 h-arc의 ‘바로 위’ 부분과 ‘바로 아래’ 부분으로만 나누어 최적해를 구한다는 것입니다. H-arc에 걸쳐있는 부분다각형은 이미 계산이 완료되었으므로, 남은 윗부분과 아랫부분에 대해서만 고려하면 되는 것입니다. 이때 left/right 부분다각형 각각에 대해 최적분할이 Fan의 형태임이 보장됩니다 (monotone polygon의 경우). 따라서 양쪽의 Fan에 의한 비용을 합하고, 가운데 h-arc 자체의 비용까지 더하면 됩니다.
그런데 h-arc의 개수가 여러 개일 경우, 어떤 h-arc부터 처리해야 할지 고민이 됩니다. 이에 대한 저자들의 직관은 ‘기준 h-arc 바로 위에서 시작하여, 그 직선을 따라 바깥쪽으로 뻗어나가는 쪽의 h-arc부터 우선적으로 처리하자’는 것입니다. 이러한 처리 순서를 결정하는 기준으로 도입된 개념이 바로 supporting weight입니다.
Supporting weight란, 주어진 h-arc $V_a$-$V_c$에 대해, 그 직선을 따라 위쪽으로 뻗어나가면서 새로 만나는 꼭지점들의 가중치 조화평균을 말합니다. 구체적으로는 다음과 같이 정의됩니다:
\[S(V_a\text{-}V_c) = \frac{C(w_a, \ldots, w_c) - w_aw_c}{(w_a:w_c) - w_aw_c}\]여기서 $C(w_a, \ldots, w_c)$는 $V_a$-$V_c$ 위쪽 부분다각형의 최적분할 비용, $(w_a:w_c)$는 $w_a$에서 $w_c$까지 시계방향으로의 가중치 누적합을 나타냅니다. 이렇게 정의된 supporting weight가 클수록, 해당 h-arc 위쪽으로 뻗어나가는 쪽에 최적분할에 유리한 꼭지점들이 많이 몰려있음을 의미합니다. 따라서 이 값이 큰 h-arc부터 먼저 처리하는 것이 타당한 것입니다.
H-arc들을 supporting weight 기준으로 정렬하기 위해, 저자들은 leftist tree를 사용한 priority queue를 고안했습니다. Arc-tree의 각 노드마다 별도의 priority queue를 두고, 그 노드의 바로 위쪽에 존재하는 h-arc들을 sup-weight 순으로 저장해 둡니다. 노드 방문 시마다 priority queue에서 top 원소를 뽑아 처리하고, 남은 h-arc들에 대해 같은 작업을 반복하는 것입니다. priority queue의 추가/삭제 연산은 O($\log n$) 시간에 수행 가능하므로, 전체 시간복잡도는 arc-tree의 노드 수에 $\log n$을 곱한 O($n \log n$)이 됩니다.
마지막으로 위 과정을 통해 모든 h-arc에 대한 부분문제가 해결되면, arc-tree의 루트에 저장된 값이 원래 다각형 전체의 최적분할 비용, 즉 행렬 곱셈의 최소 연산량이 됩니다. 시간복잡도를 보면 arc-tree 구축에 O($n \log n$), DP 계산에 O($n \log n$)으로 총 O($n \log n$)입니다. 추가로 priority queue를 병합할 때 LCA(lowest common ancestor) 알고리즘을 활용하면 O($n$)까지 개선할 수 있습니다.
이상으로 Hu-Shing 알고리즘의 동작 과정을 자세히 살펴보았습니다. 이 알고리즘은 행렬 곱셈 문제를 절묘하게 변형하여 최적부분구조(optimal substructure)를 찾아냈고, 동적계획법과 supporting weight 개념을 적절히 조합하여 O($n \log n$)이라는 준수한 시간복잡도를 달성했습니다. 특히 monotone polygon과 같은 특수한 경우를 활용하여 DP 계산을 간소화한 점, priority queue를 통해 계산 순서를 조절한 점 등 세부적인 아이디어도 인상적입니다. 이 알고리즘은 30년 넘게 O($n^3$)이 최선으로 여겨지던 행렬 곱셈 문제를 획기적으로 해결했을 뿐 아니라, 그 과정에서 볼록 다각형 분할이라는 새로운 문제를 발굴하고 정립했다는 점에서 큰 의의가 있습니다.
전체 코드 보기
죄송하지만 코드 복사 방지를 위하여 이번의 소스코드는 없습니다..
복잡한 로직과 세부 구현 사항들이 많아 코드의 이해도 쉽지 않고, 디버깅도 까다로운 편입니다. 하지만 한 번 제대로 이해하고 나면, 행렬 곱셈 순서 최적화 문제를 매우 효율적으로 해결할 수 있습니다.
이 문제를 통해 동적 계획법의 한계를 느끼고, 더 높은 수준의 알고리즘과 테크닉의 필요성을 깨달을 수 있었습니다. Hu-Shing 알고리즘을 공부하면서 알고리즘의 깊이와 아름다움을 경험할 수 있었고, 문제 해결 능력을 한 단계 더 향상시킬 수 있었습니다.
여러분도 이 문제에 도전해보시는 것을 추천드립니다. 처음에는 어려울 수 있지만, 포기하지 않고 끝까지 고민하다 보면 분명 값진 깨달음을 얻을 수 있을 것입니다. 또한, Hu-Shing 알고리즘 외에도 다양한 최적화 알고리즘들을 공부해보는 것도 큰 도움이 될 거예요.
행렬 곱셈 순서 최적화 문제를 해결하면서 알고리즘의 중요성과 깊이를 다시 한번 느낄 수 있었습니다. 앞으로도 다양한 문제들에 도전하며 알고리즘 실력을 갈고닦는 것이 목표입니다. 여러분도 함께 알고리즘의 세계에 빠져보는 건 어떨까요? 감사합니다!