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

Exercise1

행렬 곱하기 문제: Iterative solution 이 사용된다.

A와 B가 각각 nxn 행렬이라고 가정.

3번부터 7번까지가 곱하게 되는 과정. 3개의 for loop으로 구성되어 있다.

7번 라인에서 곱하게 된다. C 행렬은 A의 row와 B의 column을 모두 곱하게 되는 과정이 있다.

Time Complexity를 구하는 것은 for loop이면 구하기 쉽다. 세타 n^3이다. 그냥 n^3이라고 표현하면 안된다.

 

 

Exercise 2

Divide and conquer로 풀게 되면 Recur로 하게 된다. C라는 매트릭스를 반반 4등분을 진행한다. A와 B도 마찬가지로 Divide를 진행한다. C라는 매트릭스는 A와 B 매트릭스 그룹으로 곱하게 된다. 

Element를 하나 남길 때까지 계속 Divide를 해나간다. n = 1 이 될 때까지 나눠졌다면 그것이 Base case가 된다. 그렇지 않으면 행렬 연산을 진행하면 된다. 이때 function call은 같은 함수를 recur 하게 사용하게 된다. n == 1이 되면 return 하고 계속 이런 방식으로 진행하게 된다. C12도 동일 방식으로 진행..!!

 

Recurrence equation으로 시간 복잡도를 표현해야 한다.

 

a) recurrence equation을 구해야 한다.

n이 1일 때와 n이 1 보다 클 경우로 나눈다 1인 경우 Constant가 된고 1보다 큰 경우, 8번을 함수 호출해야 하고, 한번 함수 호출을 할 때마다 n/2 x n/2 만큼 사이즈 call을 하게 된다. 마지막으로 Combine 할 때는 얼마나 사용이 됐는지를 확인해야 한다. Combine 할 때, 더하기를 통해서 진행하게 된다. n/2 x n/2 만큼 진행을 하게 된다. 즉, 그럼 n^2만큼 더하게 된다고 보면 된다.

 

 

b) Recursion Tree

T(n)은 세타 n^2 이므로 cn^2 라고 할 수 있고 여기서, 8개의 T(n/2) 만큼 생기게 된다. cn^2은 다시 8개의 n ... 이런 방식로 T(1)까지 진행하게 된다. 먼저 진행해야 하는 것은 Recursion Tree의 Height를 구해야 한다.  위 그림처럼 Height를 구하게 되고 밑이 2인 log를 lg라고 표현을 한다. 

 

 

Master Theorem

 

 

Dynamic Programming
특별한 알고리즘이 아니라 디자인 패러다임이다. Divide and conquer, merge sort가 있고 pivot을 중심으로 하는 quick sort가 있다.
Incremental은 Insertion, Selection, Bubble sorting이 존재한다. Backtracking은 Maze Problem에서 갈래길에서 현재의 상황을
스택에 저장해서 뒤로 돌아오는 것 같은 기능을 구현하는 것이다. 최적화 문제에서 사용을 한다. 최적화된 값을 찾는 문제.
Minimization과 Maximization하는 문제에서 사용이 된다.

Optimization
shortest path Problem을 찾을 때, 서울과 부산으로 이동할 때 대전이라는 곳을 방문하기로 선택을 하면 대전부터 서울까지
가는 것 중 어느것이 Shortest인가, 부산부터 대전까지는 어느 경로가 shortest인가를 결정하게 된다. Subproblem을 생성하게 된다.
최적의 선택이 무엇인지 사실 알기 어렵다. 여러가지 방법이 있을 수 있다. 그래서 모든 경로를 다 따져보는 것이다. 선택에 따라서
어떤 것이 최단 거리인지 선택을 하게 된다. 알고리즘이라고 하기는 어렵고 Brute Force라고 한다. 모든 경로를 따지는 것이다.
이렇게 모든 경우를 따지지 않고 어떻게 최적화 문제를 푸는가를 연구한 것 중 하나가 Dynamic Program이다.

Dynamic Programming
DP는 Divide and conquer랑 뭐가 다른지 생각이 들 수 있다. Solution S를 구하는데 S보다 작은 문제의 solution을 먼저 구하게 된다.
여기까지는 Divide and conquer이다. 하지만 다른 점이 존재한다. top down 방식이 아니라 bottom up fashion 형식을 따른다.

Fibonacci Number Example
Divide and conquer는 recursive하게 풀게 되고 DP는 Iterative하게 접근한다. Divide and conquer의 경우 n부터 시작해서 0까지
내려가게 되는 top bottom 형식을 따른다. 출발 지점이 top이 된다. DP의 경우 0부터 시작해서 n까지 올라가는 bottom up
형식을 따르게 된다. 

Recalculation in Divide and Conquer
Top에서 Bottom으로 내려가는 방식, 같은 것을 여러번 계산하게 되는 구조이다. 왜냐하면 위에서 아래로 잘게 나누어 시작하기
때문이다. DP의 경우 0과 1에 값을 집어넣고 그 다음 다음 index 값에 들어가게 되는 value를 계산하는 과정을 또 다시 진행하는 경우가
존재하지 않다. 

Divide and Conquer vs DP
Divide and Conquer는 같은 계산 과정을 여러 번 진행하게 된다. DP의 경우 한 번 계산된 값을 계속 활용해서 사용하기 때문에
연산량이 더 적다. 

Matrix Chain Multiplication
행렬의 곱을 살펴보자. 먼저 1과 2계산 할 필요 없이 2와 3을 먼저 곱해서 차이가 없다는 것이다.

The cost of Multiplying Two Matrices
A: 2x3 B: 3x4라고 하면 2x4 행렬이 나온다. 곱셈이 총 p x q x r 만큼 곱셈이 진행된다. 

The cost of Multiplying Three Matrics
곱하는 순서에 따라 다음과 같이 곱셈의 크기가 달라진다. 

More Matrices More ways to Parenthesis
행렬의 개수가 늘어날 수록 괄호를 치는 방법이 매우 다양해진다. 어떤 방법을 택하는지에 따라 곱하기 횟수가 달라진다.

Example
작게는 6500이번 많게는 47500을 계산해야 되는 연산량의 차이가 존재한다. 모든 경우를 다 따지는 경우는 Brute Force가 된다.
DP는 그것보다 적고 빠른 방법으로 진행하게 된다. 

Number of Parenthesizations
행렬이 n개 일때 곱에 대한 것을 생각해보자. A1과 A2를 곱하는 방법. 일반적으로 n개의 행렬을 곱하는 방법은 P1Pn-1, P2Pn-2...
Pn-1P1 까지 진행하게 된다. 괄호를 치는 방법에 대한 것으로 해석할 수 있다. Pn은 2^n-1 보다 크거나 같다.  2^n / 2보다 크거나 같은 것이므로
빅 오메가 2^n으로 표현할 수 있다. Brute force의 경우 2^n 정도 계산을 해야 한다는 것이다. n이 조금만 커지더라도 어마어마 하게
커지게 된다.

Optimal Matrix chain multiplication
곱하기의 횟수를 최소하는 방법을 하는 것이 BP로 하게 되면 모든 경우를 따져야 하고 Computational infeasible하다고 표현한다.
최소한 2^n만큼 걸린다는 것이다.

Recalculation:  The Source of All Evil
한 번 계산한 것이 반복 계산된다는 것이다. 

Memoization: Avoiding Recalculation
DP의 방식과 동일하지만 Top down 방식으로 진행하게 된다.

Fibinacci Number
Recursion을 이용하는 것은 동일하지만 다른 점은 원하는 값이 존재한다면 true라면 저장된 값을 불러오므로써 recalculation을 안하게 할 수 있다.
TOP DOWN 방향성은 유지시킨다. 

Structure of Optimal Solution
어떤 경우에 DP로 풀 수 있는지를 살펴보고자 한다. Ai부터 Aj 까지의 행렬을 곱하게 될 때 Ak라는 행렬을 기준으로 괄호를 나눌 수 있고
계속 비슷하게 나뉘어 나갈 수 있다. 

포항부터 서울까지 간다고 해보자. 포항에서 대구, 김천, 대전, 청주, 수원을 거쳐서 서울을 갔다고 하자. 이게 Optimal 하다고 가정.
포항에서 대전으로 가고 대전에서 서울로 가는 세부 문제가 또 생기게 된다. 여기서 또 포항에서 대전으로 가게 되는 문제의 Sub Problem이 생긴다.
Sub 문제를 해결하는 Optimal 한 방법도 Optimal하게 정해져 있다는 것이다. 

When can we apply Dynamic Programming
Optimal Substructure, sub Problem도 Optimal한 방법을 가지고 있다.
Optimal Overlapping Subproblems, 작은 문제를 가지고 있다. 

Princilple of optimality