그리디 알고리즘

그리디 알고리즘이란?

 

현재 상황에서 지금 당장 좋은 것만 고르는 방법이다. 이 알고리즘도 어떤 특정 코드가 있는게 아니다. 문제 해결 방식 중 하나에 불과. 사실 가장 간단한 문제 해결 방식인데, '현재 상황에서 지금 당장 좋은 것만 먼저 고르는 방법'이다. 일반적으로 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는지를 테스트하는 것이다.

 

그리디 알고리즘의 적용

 

그리디 알고리즘에서는 정당성 분석이 중요하다. 즉, 단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해에 도달할 수 있는지를 검토해야 한다. 물론 그리디 알고리즘 문제는 일반적인 상황에서 최적의 해를 보장하지는 않는다. 하지만 코테에서는 탐욕법으로 얻은 해가 최적의 해가 되도록 출제한다. 즉, 단순히 가장 좋아보이는 것을 반복적으로 선택하는 행동으로 최적의 해가 되는 방식을 추론 & 검토 할 수 있어야 한다는 것.

 

참고자료 : https://www.youtube.com/watch?v=2zjoKjt97vQ