그리디 알고리즘

탐색은 보통 (1) 완전탐색 (2) DP, 분할정복(Divide conquer), ... (3) 그리디 로 분류됩니다.

 

이 중에서 (1) 완전탐색은 말 그대로 모든 경우의 수를 전부 무식하게 확인해보는 방법입니다.

(2) DP, 분할정복은 큰 문제를 잘게 쪼개어 각 경우를 탐색한 뒤, 전체적으로 결과를 확인하여 답을 도출하는 방법입니다. 이 또한 결국은 전체 경우를 전부 확인하는데, 스마트하게 탐색하는 느낌입니다.

 

마지막으로, (3) 그리디는 그 순간 순간의 최선을 선택하는 알고리즘으로, 쉽게 말해서 여러 경우의 수 속에서 정답이 될 수 밖에 없는 경우가 명확할 때, 그 경우만 탐색하는 방법입니다. 매 순간의 선택이 무조건 정답으로 향한다는 보장이 있어야 그리디 알고리즘이 적용됩니다.

 

그리디는 매번 선택하는 것이 최신이라고 확신되는 경우에만 적용할 수 있으므로, 만약 그게 아니라면 다른 적절한 탐색 알고리즘을 적용해야 합니다.