[자료구조] 5. 탐욕 알고리즘(Greedy Algorithm)& 동적계획법(Dynamic Programming)

1. 탐욕 알고리즘(Greedy Algorithm) 

- 최적회를 구하는데 사용되는 근사적인 방법, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식 -> 즉 최종적인 해답에 도달 

- 현재 상황에서 가장 좋아 보이는 답을 선택하는 방법

- 각 부분에서 최적을 선택하면 전체에서도 최적이 될 것이라는 가정을 전제로 함

- 선택은 항상 하위 문제에 대한 해답이 나오기 전에 선택됨 

 

 

대표적인 문제 

ex) 배낭채우기문제 

 

최소신장트리(MST, Minimum Spanning Trees) 

https://en.wikipedia.org/wiki/Minimum_spanning_tree

- 신장트리(Spanning Tree) ? 사이클을 형성하지 않고 그래프의 모든 정점이 간선으로 연결되어 있는 것 

- 특징

1. 간선의 가중치 합이 최소여야 함

2. n개의 정점을 가지는 그래프에 대해 반드시 n-1의 간선만을 사용

3. 사이클이 포함되서는 안됨 

 

 

 

1.1 Prim의 MST 알고리즘 = 프림 알고리즘

-정점의 최선값을 선택하여 MST 문제를 해결하는 알고리즘 

 

 

1.2 Kruskal 알고리즘 

- 간선의 가중치 값을 정렬하여 MST 문제를 해결하는 알고리즘 

 

탐욕선택 (Greedy-choice property)	동적 프로그래밍 (Dynamic Programming)
- 하위 문제를 풀기 전에 선택을 한다 - 항상 하나의 문제만을 고려한다.	- 하위 문제를 풀고 나서 선택을 한다 - 동시에 여러개의 하위 문제를 고려한다.

 

 

 

 

 

---

2. 동적계획법(Dynamic Programming)

- 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법

- 일반적으로 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것

- 최단 경로 문제, 행렬의 제곱 문제 등의 최적화에 사용

 

 

 

 

<출처> 

1. ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95

2. ko.wikipedia.org/wiki/%ED%83%90%EC%9A%95_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

탐욕 알고리즘 - 위키백과, 우리 모두의 백과사전

3. T아카데미 - 컴퓨터 알고리즘 기초 19강 탐욕 알고리즘