그리디 알고리즘(Greedy Algorithm)

그리디 알고리즘은 "매 선택에서 지금 이 순간 가장 최적의 답을 선택하여 결과를 도출"하는 방법이다. 어찌보면 문제가 생길 가능성이 높은 알고리즘이다. 당장의 선택만에서는 최적으로 될 수 있으나 전체적으로 종합해보았을때는 최적이 된다는 보장이 없다 조삼모사.

그러나 그리디알고리즘이 통하는 경우가 있다. 다음 두 조건이 만족하면 그리디알고리즘을 써도 무관하다.

 

1. 선택 조건(greedy choice property)

2. 최적 부분 구조 조건(optimal substructure)

 

이는 한번의 선택이 미래의 선택에 무관해야하며 매 순간의 최적해가 곧 문제에 대한 최적해여야 한다는것을 뜻한다.

그리디 알고리즘은 100%최적해를 보장해주지 않는다. 다만 어느정도 적절한 수준의 해답을 알려주는데, 최적이 확실치 않은 상황에서는 답을 찾을 수 있는것 또는 적절한 답에 도달하는것을 목적으로 쓸 때도 있다.

그러나 선택조건과 최적부분구조조건이 완벽히 만족한다는것이 보장될때, 최적해만을 찾아가므로 다이나믹프로그래밍이나 DFS, BFS같은 경로찾기문제보다 빠른 속도로 최적의 답을 도출 해낼 수 있다는것이 가장 큰 장점이다.