[Algorithm] 그리디(탐욕) 알고리즘

Posted: 2023.05.03     Updated: 2023.05.03

그리디 알고리즘

현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.
일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.
단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토하는 정당성 분석 과정이 필요하다.

예시

루트 노드에서 시작하여 거쳐가는 노드 값의 합을 최대로 만들고 싶은 경우

단순히 매 상황에서 큰 값만 선택하는 방법을 반복하여 구할 수 있다.

특징

일반적인 상황에서 그리디는 최적의 해를 보장할 수 없는 경우가 많다.
따라서 실제 프로그램에서는 그리디 알고리즘을 사용해도 충분히 최적의 해에 가까운 값 혹은 최적의 해를 얻을 수 있을 때 사용한다.
그러나 코딩 테스트에서는 그리디 문제가 출제된다면, 단순히 탐욕법을 사용해야 한다는 것을 추론해야 풀 수 있도록 출제된다.