그리디 알고리즘(Greedy Algorithm)

기본 개념

---

그리디 알고리즘(greedy algorigthm, 탐욕 알고리즘)이란 선택의 상황에서 현재 가장 최선이라고 생각되는 것을 선택해 나가 결과를 도출하는 알고리즘이다. 현재 최적인 값만 탐색하면 되기 때문에 계산 속도가 빨라 실용적이라는 장점이 있으나, 최종 값이 최적 값이라는 보장이 없다는 단점이 존재한다.

그리디 알고리즘을 사용할 때에는 두 가지 조건이 만족되어야 한다.

• 탐욕 선택 속성(greedy choice property)
• 최적 부분 구조(optimal substructure)

 

'탐욕 선택 속성'은 현재 선택이 다음 선택과 무관해야 한다는 조건이고, '최적 부분 구조'는 현재 최적 선택이 전체 최적 선택이 되어야 한다는 조건이다. 두 조건을 만족하지 않다면 그리디 알고리즘을 사용했을 때 최적 값을 구하지 못하는 경우가 발생한다.

 

 

 

예시

---

예를 들어 A에서 B 혹은 C를 거쳐 D로 간다는 상황을 가정해보자. A와 B 사이의 거리는 10이고, A와 C 사이의 거리는 100다. 그리고 B와 D 사이의 거리는 1000이고 C와 D 사이의 거리는 10이다.

그리디 알고리즘에 따르면 현재 가장 최선인 방식을 선택해야 한다. 때문에 A에서 출발할 때, B와 C 중 거리가 더 가까운 B를 선택해야 한다. 하지만 B에서 D에 간다면 총거리는 1010이 되고, C에서 D에 간다면 총거리는 110이 된다. 최종적으로 그리디 알고리즘을 통해 선택했지만 최적해를 구하지 못하는 상황이 된다.

 

 

 

예시 문제

---

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정