Lesson 7 : Case studies in Algorithms

1. 많은 것을 배웠지만, 많은 것을 까먹었다고 합니다... 이래서 복습이 중요합니다.

2. 근본 문제에 대한 분명한 이해를 해야 합니다.

 

1. 가장 짧은 길을 찾는 문제는 그래프에서 가장 짧은 path를 찾는 것과 같은 문제이다.

2. 그래프의 타입에 따라 이 path를 계산하는 방식에는 차이가 있다. 가중치 그래프라면 가중치를 계산해야 하지만, 그렇지 않다면 엣지의 수를 계산해야 한다.

3. 비가중치 그래프는 BFS(Breath First Search)와 같다.

 

1. Weighted undirected graph일 때, Shortest path를 차즌 문제를 Dijkstra's Algorithm이라고 부른다.

2. 이때 모든 엣지에 ditance value를 주게 된다.

3. 그리고 distance는 엣지의 가중치의 총합이다.

4. Dijkstra's Algorithms의 일반적인 적용은 min priority queue다. 

 

5. 시작하는 노드는 0의 거리 값을 가지게 되고

6. 스타딩 노드에서 근접한 노드를 선택할 때, 가중치가 더 적은 값을 선택한다.

7. 노드 선택의 순간마다, 항상 작은 값을 선택하기 때문에 이러한 성격의 알고리즘을 Gredy하다고 한다.

1. 다이제스타라의 런타임은 벌텍스의 제곱이다.

2. 가장 최적화 되었을 때의 런타임은 아래와 같다.

 

 

 

1. 가방에 넣어야 할 물건에 무게가 있고, 값이 있다고 하자. 이 때 문제는 무게 제한 안에서 어떻게 물건의 값의 총합을 최적화 하는 것이냐다.

 

2. 값이 큰 것부터 할 수도 있겠지만, 그렇게 했다가 무게 제한을 초과해 버릴 수 있다.

 

3. 느리지만, 그래도 정확하게 하기 위해서는 가능한 모든 조합을 살펴 보는 것이 옳다. 이러한 것을 Brute Force Solution이라고 한다.

 

1. 런타임은 위와 같다.

 

1. 좀 더 빠른 방법, 똑똑하게 생각해보자. 만약 우리가 가능한한 적은 무게에 대해 값을 최적화 한다면 어떻게 될까? 그리고 우리가 가지고 있는 무게 제한이 될 떄까지 아이템을 추가한다면 어떻까?

 

 

 

1. 햇갈리니 차근차근 이해해 보자.

2. 룰은 간단하다. 해당 무게 에 대한 값을 최적화 하는 것이다.

3. 무게가 2이고 값이 6인 아이템이 들어왔다면, 무게가 2 이상인 무게에 대한 값은 모두 6이 된다.

4. 무게가 5이고 값이 9인 아이템이 들어왔다면, 무게가 5 이상인 아이템에 대하여 값은 모두 9가 된다.

5. 무게가 4이고 값이 5인 아이템이 들어왔다면, 무게가 4일 때  이미 값이 6이기 때문에 갱신할 무게 4의 최대 값을 바꿀 필요가 없다.

6. 하지만 무게 4와 무게 2의 아이템이 같이 들어왔을 때 값은 11일 수 있기 때문에, 무게 6의 최대 값은 11로 고쳐줘야 한다.

 

1. 런타임은 무게 제한 곱하기 아이템의 수다.

2. 이러한 방법은 Pseudo polynomial time solution이라고 한다.

3. 레알 폴리노미얼 솔루션은 W같은 것이 없다.

 

1. 세부 문제로 부셔서 문제를 푸는 것이 훨씬 빠르다. 이것이 다이나믹 프로그래밍이다.

2. 최대한 간단한 질문과 답으로 이루어진 형식으로 바꾼 뒤, 최적합을 찾는다! 이것이 다이너믹 프로그래믹의 핵심이다.

 

 

1. 아주 사소한 문제에 대한 답을 룩업테이블에 기록하는 것으로 부터 다이나믹 프로그래밍이 시작된다.

2. 그리고 차근차근 복잡함을 더해간다.

 

 

1. 다이나믹 프로그래밍의 또 다른 특징은 복잡성을 더해갈 떄마다 등호가 사용된다는 것이다.

 

1. 다이나믹 프로그래밍의 숨겨진 강점이 이것이다. 룩업테이블을 이용하기 떄문에, 이미 계산한 문제에 대해서 다시 계산할 필요가 없다.

 

 

1. 문제를 발견하고, 그 문제를 다이나믹 프로그래밍을 이용해서 푸는 것이 중요하다.

2. 내가 이 문제를 더 작은 문제로 쪼갤 수 있을까? 이 문제에 답할 수 있다면, 당신은 다이나믹 솔루션의 답을 얻은 것이다.

 

1. Traveling Salesman problem은 NP-Hard라고 불린다. 이 문제는 폴리노미얼 타임으로 해결할 수 있는 알고리즘이 없다.

 

1. 넵섹 문제 또한 NP-Hard인데, 그 문제를 해결 했던 것처럼, Pseudo Polynomal Time을 이용할 수 이있다.

 

2. 문제가 복잡하기 떄문에 2가지의 알고리즘이 해결책으로 제시된다.

 

 

 

1. 첫 번째가 Exact Algoritms으로 Polynomial time으로 일어나진 않지만 정확한 답으로 얻을 수 있다.

2. 두 번째는 Approximation Algorithms로 항상 최적해를 찾지는 못하지만, 일반적으로 최적에 근사한 값을 찾을 수 있는 알고리즘이다. 적당한 횟수의 런타임을 가지며, 대부분이 Polynomial한 시간을 가진다.

 

3. Brute Force solution Exact Algoritms과 같은데 정확한 답을 찾을 순 있지만, 분명히 더 오래 걸린다는 단점이 있다.

4. TSP(Travelling Salesman Problems) 문제를 해결하기 위한 알고리즘 중 하나가 HEld-Karp 알고리즘이다.

 

 

1. 정확한 답을 제시하지 못하는 Approximation 알고리즘이지만, 이에 대한 많은 연구가 진행 중에 있다.

2. 스타딩 노드를 루트로 트리 구조를 만들며 길을 찾는 것인데, 이 Christofiedes 알고리즘은 최적해보다 50%이하로 긴 것을 보장한다.