그리디 알고리즘

탐욕 알고리즘 (Greedy algorithm)은 최적해를 구하는 데 사용되는 방법이다.

현재를 기준으로 각 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행된다.

일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다.

하지만 코딩 테스트에서의 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황이기에, 이를 추론할 수 있어야 한다.

추론 과정

• 현재 선택이 미래 선택에 영향을 미치지 않는다면 그리디 알고리즘을 통해 해결 할 수 있다.
• 각 부분의 최적의 해가 모였을 때, 전체의 최적의 해가 된다면 그리디 알고리즘을 통해 해결할 수 있다.

시간복잡도

O(K)

참고 -