[알고리즘] Greedy Algorithm

Greedy Algorithm 이란?

 

탐욕적인 알고리즘이라고도 하며, 결정을 해야 할 때마다 그 순간에 최적이라고 생각되는 것을 해답으로 선택하는 방식

 

문제점

 

그 순간의 선택은 당시(local)에는 최적이다. 그러나 최종적인(global) 해답을 만들었을 때,

그 해답이 최적이라는 보장이 없다. 따라서 항상 최적의 해답을 주는지 검증해야 한다.

(대표적으로 0-1 Knapsack문제가 그러하다.) 

 

 

1. Prim's Algorithm

 

임의의 정점(vertex)에서 가중치가 가장 작은 간선(edge)을 선택,

 

선택된 정점(vertex)와 연결된 간선(edge)들 중에 가장 가중치가 작은 것들을 선택(단, cycle을 만드는 경우는 제외)

 

 

 

 

2. Kruskal's Algorithm

 

그래프의 모든 간선(edge)중에서 가중치가 가장 작은 것부터 차례대로 선택한다(단, Cycle을 만드는 경우는 제외)

 

3. Dijkstra Algorithm

 

가중치가 있는 방향그래프에서 임의의 두 노드 사이의 최단거리를 구하는 알고리즘. 

 

 

 

그리디 관련 문제

 

• 11047 동전 0
• 1931 회의실배정
• 11399 ATM
• 1541 잃어버린 괄호
• 2217 로프
• 1946 신입 사원
• 1700 멀티탭 스케줄링
• 1969 DNA
• 강의실 배정
• 시험 감독
• 캠핑 문제
• 모두의 마블