[Greedy] 그리디 알고리즘

🥭 그리디 알고리즘

그리디(Greedy) 알고리즘은 탐욕법이라고도 하며, 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.

 

그리디 알고리즘을 이용하면 매 순간 가장 좋아 보이는 것만 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 즉, 현재의 최적 선택을 번복하지 않는다. (선택한 것을 버리고 다른 것을 취하지 않는다)

=> 이는 다이나믹 프로그래밍과 가장 큰 차이점으로, 모든 단계를 끝내고 이전으로 돌아가 다시 생각하는 과정이 없다는 의미

• 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다고 함!

 

🥭 그리디 알고리즘 코딩테스트 유형

1. 그리디 알고리즘 문제는 문제 유형을 미리 외우지 않아도 해결할 가능성이 높다고 한다.

• 이는 그리디 알고리즘이 다양한 방식으로 출제되기 때문
• 다익스트라 알고리즘 같은 특정 사례를 제외하면, 단순히 암기로 모든 문제를 해결하는 것은 어려움

2. 대부분의 그리디 알고리즘 문제는 창의력, 즉 최소한의 아이디어를 떠올리는 능력을 요구한다.

 

3. 문제에서 종종 '가장 큰 순서대로' 혹은 '가장 작은 순서대로'와 같은 기준을 암시적으로 제시한다.

 

4. 그리디 알고리즘 문제는 종종 정렬 알고리즘과 함께 출제된다.

 

 

🥭 그리디 알고리즘 vs 다이나믹 프로그래밍

다이나믹 프로그래밍

 

• 전체 문제를 여러 하위 문제로 나누어 각각의 최적 해법을 찾고, 이를 기반으로 최종 해법을 도출.
• 항상 최적의 해를 보장하며, 모든 가능한 경우를 고려함

그리디 알고리즘

 

• 각 단계마다 지역 최적 해를 선택해 문제를 점차 작게 만든다.
• 항상 최적의 해를 보장하지 않으며, 한 번 선택한 해법을 되돌릴 수 없다.
• 일반적으로 다이나믹 프로그래밍보다 빠른 성능을 보인다.

--> 두 알고리즘은 문제 해결 접근 방식이 상반됨!