https://www.acmicpc.net/problem/11066 이전 포스트로 "행렬 곱셈 순서"에 대해서 두 가지 방식의 다이나믹 프로그래밍으로 문제를 풀어봤다.https://gg4ever1724.tistory.com/39 [C++] 11049: 행렬 곱셈 순서https://www.acmicpc.net/problem/11049 두 가지 방법으로 연습해보자.알고리즘 분류다이나믹 프로그래밍  문제설명 행렬은 교환법칙이 성립하지 않지만, 결합법칙은 성립한다. 그래서 예를들어, ABC의gg4ever1724.tistory.com 이 포스트처럼 이번 파일 합치기 문제도 두 방법으로 풀되, 우선적으로 상향식 방법을 연습하자. 알고리즘 분류다이나믹 프로그래밍 문제설명 문제접근 어떻게 보면 행렬 곱셈 순서보다는 덜..

https://www.acmicpc.net/problem/11049 두 가지 방법으로 연습해보자.알고리즘 분류다이나믹 프로그래밍  문제설명 행렬은 교환법칙이 성립하지 않지만, 결합법칙은 성립한다. 그래서 예를들어, ABC의 곱을 구할 때에는 B x A x C 이렇게 하면 안되지만,A x (B x C) 이렇게 하면 된다는 이야기다.  이 과정에서 행렬 곱을 구할 때 가장 작은 곱셈의 연산 횟수의 최솟값을 구하자는 것이다. 아이디어는 간단하고, 실제 최적화 작업에도 도움이 될 만한 로직이다. 문제접근우선 완전탐색으로 이 문제를 풀 수 있을지! 에 대해 알아보자.for loop 을 돌면서 괄호를 잡을 것이다. 우선 ABCD의 곱을 구한다고 가정하고, 현재 index = B 라고 생각하자. 그렇다면, 여기에서는..