19강. 탐욕 알고리즘

[ 목차 ]

1. 탐욕 알고리즘

2. 탐욕 선택

3. 동적 프로그래밍

4. 가중 무방향성 그래프

5. 신장트리

6. 최소신장트리

 

1. 탐욕 알고리즘

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

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

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

 

2. 탐욕 선택

1) 하위 문제를 풀기 전에 선택

2) 항상 하나의 문제만을 고려

 

3. 동적 프로그래밍

1) 하위 문제를 풀고 나서 선택

2) 동시에 여러 개의 하위 문제를 고려

 

4. 가중 무방향성 그래프

1) G = (V,E)

2) 간선 집합에 속하는 각 간선(u,v)는 w(u,v)를 가짐

 

5. 신장트리

1) 트리가 그래프 G의 모든  정점을 포함할 대 그래프 G에 속하는 트리의 간선을 선택한 것

 

6. 최소신장트리

1) 신장트리의 비용

2) 최소신장트리 문제 : 비용이 최소가 되는 신장트리를 찾는 문제

3) 최소신장트리는 한번에 하나의 간선이 늘어남

4) 간선(u,v)을 집합 A에 추가하고 AU{(u,v)}가 최소시장트리의 일부가 되는지 확인

5) 이때, 이런 간선을 안전간선이라 지칭

 

7. 프림 알고리즘

1) 현재 시작하는 정점을 기준으로 인접한 정점들을 추가하는 것