Talk is cheap. Show me the code.

Explaindynamic programming 기법 중 하나이며 주어진 연속되는 행렬의 곱셈에서 최적의 방법을 찾아내는것이 목표이다.\(q*p,p*r\) 크기의 행렬의 곱셈 연산의 횟수는 \( q*p*r \) 인점을 기억해야 한다.기본적으로 행렬의 곱은 associativity하므로 연속되는 행렬의 곱 ABCD 에 대해\(((AB)C)D = ((A(BC))D) = (AB)(CD) = A((BC)D)\)가 성립한다. 이때 각각의 연산마다의 곱셈 연산의 횟수는 다르므로 이중에서 최소 연산 횟수를 가지는 방법을 찾아야 한다. 예를 들어 \(A = 10*30, B = 30 * 5, C = 5 * 60 \) 의 크기를 가지는 행렬의 곱셈을 진행 할때$$(AB)C = (10*30*5) + (10*5*60) = 1..

ExplainFloyd-Warshall algorithm 또는 Floyd's algorithm 이라고 불리우며 negative cycles을 가지지 않은 weighted graph에서 임의의 두 vertex 사이의 최단 거리를 구하는 알고리즘이며 \(\Theta(n^3) \) 의 시간복잡도를 나타내며 optimal algorithm의 한 종류이다.Notation\(N :\) vertex 의 개수\(W :\) 인접 vertex 간의 weight \( |N^2| \) 이며 인접하지 않은 vertex 간의 거리는 \(\infty\)\( D_{(k)}[i,j] = \) from i to j 의 경로중 k 이하의 vertex만을 통과하여 얻을 수 있는 최단거리\( D_{(0)}[i,j] = W[i,j] \) 0이..

Explain.어떤 양의 정수 X의 자리수가 등차수열을 이룬다면, 그수를 한수라고 한다.등차수열은 연속된 두개의 수의 차이가 일정한 수열을 말한다.N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오.Input자연수 N ( N

Explain피보나치 수는 0과 1로 시작하며, 다음 피보나치 수는 바로 앞 두 피보나치 수의 합이된다. (\( F_n = F_{n-1} + F_{n-2} \))모든 문제를 Recursion 한 방식으로 생각하는 것뿐만 아니라 그 이후 반드시 다른방식(Iteration, Memozation) 등 과 비교하여 최적의 방법을 찾아내는 작업도 병행되어야 하는 점을 알아야 된다.이 문제는 Recursion 방식의 큰 위험성에 대해 파악할 수 있는 문제이다.Formula$$\begin{equation*} F_n=F_{n-1}+F_{n-2}, \quad F_1=1, \quad F_2=1 \end{equation*}$$ $$\begin{equation*} 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ..

Explain수열의 합을 구하기 위한 방법 정리.문제 해결 시 Recursive한 해결 방법을 찾아내기 위한 노력할 것.Iteration, Recursion 2가지 방식으로 풀이 후 비교. 문제 해결 시점에서 Iteration, Recursion 각각의 방법을 도출한 뒤 최적의 방법을 선택할 것.문제마다 Iteration방식이 최적 일수도 있고 Recursion 방식이 최적일 수가 있다. $$S(n) = \sum_{i=1}^{n}i = 1 + 2 + ... + n $$Iteration //Iteration method. int S_Iteration(int n) { int i; int sum = 0; for(i = 1; i