알고리즘 4주차 월요일 강의

 

Optimal Substructure
각각의 점을 찍으면 세로의 좌표부터 가로의 좌표로 가는 최단 거리를 나타내게 된다. Diagonol 한 것은 자기 자신에 대해 대응하므로 0으로 채워져있다. (1,3) 부터는 두가지 방법이 존재한다. 괄호를 할 수 있는 경우의 수로 나뉠 수 있다. 마지막 Solution은 (1,6)에 위치하게 된다. (3,6)의 경우, A3부터 A6까지 곱할 수 있는 경우를 생각해보자. Sub Problem에 대한 Solution이 존재해야 하고 그것들이 Optimal 해야 한다. Optimal Solution을 구할 때 이 전의 Sub Problem의 Solution은 Optimal 하다는 가정을 가지고 계산을 하므로 다시 계산하지 않아도 되는 Bottom up 방식이다. 

 

 

Optimal Substruction
Bottom 부터 시작해서 쭉쭉 올라가고 그때의 구한 값들을 계속해서 사용하게 된다. Optimal한 Solution의 값이다. 

 

 

Development of DP algorithms
optimal substructure를 가지고 있는지 확인을 해야 한다. 방금 살펴본 행렬의 곱의 경우 A1부터 An까지 구하는데 Sub Problem을 나누는 경우가 이를 확인하는 과정이 된다. 두 번째로, Sub problem과 어떤 관계를 가지고 있는지 수식을 정해야 한다. 세 번째로, 정한 식에 따라서 Solution을 결정한다. 계산한 값이 우리가 원한 solution과 다를 수 있다. MCM 문제에서 곱하기 횟수가 가장 적은 것을 중심으로 했지만 실제로 우리가 원한 것은 어떻게 Split을 하는 지를 알고 싶었던 것이다. 

 

 

 

Step 2
m[i,j] 라는 term을 정의한다. Ai 부터 Aj까지 행렬을 곱하는데 필요한 최소 계산 개수이다. 아까 square 하나하나가 M[i,j] 가 된다. Split이 Ak와 Ak+1에서 일어났다고 하면 Diagonal한 곳에는 0의 값이 들어간다(곱할 필요가 없으므로). AiAi+1,,, Ak Ak+1 ,,, Aj Split이 k와 k+1 사이에서 일어난다. 

 

 

Computing the optimal costs
이전에 사용한 값과 행렬의 크기에 따른 곱셈의 횟수를 더하게 된다. p가 행렬의 크기가 된다. k = 3,4,5일때 곱셈의 횟수에 따라서 min 값 선택해서 3,6에 저장을 해 놓는다.