[알고리즘] 탐욕 알고리즘(Greedy Algorithm) - 하나몬

[Java/알고리즘] 그리디 알고리즘(탐욕법, Greedy Algorithm) 이해하기

탐욕 알고리즘이란?

매 선택 시점에 가장 좋아보이는 선택을 하여, 최종적인 해답에 도달하는 방식이다.

• 항상 최적의 해를 보장하지는 않는다.
• 어느 정도 최적에 근사한 값을 빠르게 도출할수 있으므로 근사 알고리즘으로 사용할 수 있다.

탐욕 알고리즘을 적용하려면, 문제가 다음 두 가지 조건을 성립해야 한다.

• 탐욕적 선택 속성 (greedy choice property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
• 최적 부분 구조 (optimal substructure) : 전체 문제의 최적 해결책을 찾기 위해서는, 먼저 그 문제를 구성하는 더 작은 부분 문제들의 최적 해결책을 찾아야 하며, 이러한 부분 문제들의 최적 해결책들을 결합하여 전체 문제의 최적 해결책을 얻을 수 있어야 한다.

탐욕 알고리즘 예시:

• 최소 신장 트리 : 크루스칼 알고리즘과 프림 알고리즘
• 집합 커버 문제 : 가능한 적은 수의 집합을 선택해 전체 집합을 커버하는 문제