[개념 정리] 그리디 알고리즘

[YubinShin]

그리디

원리가 매우 간단합니다.
현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘 입니다.
그 시점에서 최선의 상태를 계속 고르는 것.
하지만 치명적인 단점은 최적의 해를 보장하지 않는 것입니다.

시간복잡도

최적의 선택을 결정하는 데 필요한 계산 과정과 전체 과정에서의 반복 횟수가 시간 복잡도를 결정합니다.

일반적으로 그리디 알고리즘의 시간 복잡도는 다음과 같은 요소에 의해 결정됩니다:

선택 과정: 각 단계에서 최적의 선택을 결정하는 데 걸리는 시간.
반복 횟수: 최적의 선택을 반복하는 횟수.
예를 들어, 간단한 그리디 알고리즘인 '동전 교환 문제'에서는, 가장 큰 단위의 동전부터 사용하여 금액을 맞추는 방식으로 해결합니다. 이 경우, 각 선택은 O(1)의 시간이 걸리고, 전체 금액에 따라 반복 횟수가 결정되므로 전체 시간 복잡도는 O(n)이 될 수 있습니다.

다른 예로, '간선 선택을 통한 최소 스패닝 트리 생성' 같은 문제에서는 선택 과정이 더 복잡하고, 정렬이나 힙 자료구조를 사용할 수 있으므로 시간 복잡도가 O(E log E) 또는 O(E log V)가 될 수 있습니다 (E는 간선의 수, V는 정점의 수).

따라서 특정 그리디 알고리즘의 시간 복잡도를 알기 위해서는 해당 알고리즘의 세부 구현을 이해해야 합니다.

원리

1. 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.
2. 적절성 검사 : 현재 선택한 해가 전체 문제의 제약조건에서 벗어나지 않는 지 검사한다.
3. 해 검사 : 현재까지 선택한 해 집합이 문제를 해결할 수 있다면 프로세스를 종료하고,
   해결할 수 없다면 1로 돌아가서 반복합니다.