[알고리즘] 그리디 알고리즘이란?

[공지사항] 알고리즘 카테고리 포스트 살펴보기

그리디 알고리즘이란?

그리디 알고리즘이란 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 알고리즘을 의미한다.

매 순간순간 최적의 해답을 골라서 선택해 진행해야 하는 것인데,

내 기준에서는 이것을 언제 적용해야 할지 알아내는게 굉장히 힘들었다.

당장의 선택에서는 최적이지만, 이 방식을 고수했을 때 정답에 도달해서 모든 테스트케이스에서 최적이 될 것이라는 보장이 없기 때문이다.

그리디 알고리즘은 부분의 최적해들의 집합이 곧 전체 문제의 해답이 될 때 사용할 수 있다.

언제 적용해야 하는가?

그리디를 적용하여 최적해를 구하려면 현재의 선택이 이후의 선택에 영향을 주어서는 안된다.

또한, 매 순간의 최적해가 문제 전체의 최적해여야 한다.

나무위키에 나온 위 조건을 만족하는 문제 유형은 다음과 같다.

최적 부분 구조, 결정 트리 학습, 활동 선택 문제, 거스름돈 문제, 최소 신장 트리, 다익스트라 알고리즘, 허프만 코드, 크루스칼 알고리즘

다만 문제에 딸려있는 제약 조건으로 인해 그리디를 적용할 수 없는 경우도 있고,

일부분에서만 그리디를 활용해야 하는 경우 혹은 더 나은 해결책이 있는 경우도 존재한다.

그리디 알고리즘 문제 풀이

모든 문제는 자바를 활용해서 구현하였다.

[백준 2875번] 대회 or 인턴