그리디 알고리즘(Greedy Algorithm) 이란?

각 단계에서 최적의 선택을 하여 전체 문제의 최적해를 구하는 알고리즘.
항상 최적해를 보장하지 않지만, 많은 경우에 대해 빠르고 간단한 해법을 제공. 특히, 그리디 알고리즘이 최적해를 제공하는 문제를 탐욕적 최적 부분 구조를 가진다고 함.

1. 문제 분해 : 문제를 여러개의 하위 문제로 분할
2. 그리디 선택 : 각 단계에서 현재 상황에서 최적인 선택을 함
3. 문제 해결 : 이러한 선택을 반복하여 전체 문제를 해결

그리디 알고리즘의 대표적인 예와 시간 복잡도

거스름돈 문제

주어진 금액을 최소한의 동전 갯수로 거슬러 주는 문제. 예를들어, 1260원을 거슬러 줄 때, 500원, 100원, 50원, 10원 동전을 최소한으로 사용

1. 그리디 접근
   가장 큰 단위의 동전부터 사용하여 남은 금액을 줄이는 방식으로 최적해를 구함

2. 시간 복잡도
   -각 동전에 대해 나눗셈과 나머지 연산을 한 번씩 수행
   -동전의 종류가 고정되어 있다면 O(1)의 시간 복잡도를 가짐
   -동전의 종류가 n개라면 O(n)의 시간 복잡도를 가짐

활동 선택 문제(Activity Selection Priblem)

여러 활동이 주어졌을 때, 서로 겹치지 않게 최대한 많은 활동을 선택하는 문제.
각 활동은 시작 시간과 종료 시간이 주어짐

1. 그리디 접근
   종료 시간이 빠른 활동부터 선택하여 최대한 많은 활동을 선택

2. 시간 복잡도
   -활동을 종료 시간 기준으로 정렬하는데 O(n log n) 의 시간이 필요
   -정렬 후, 각 활동을 선택하는데 O(n)의 시간이 필요
   -총 시간 복잡도는 O(n log n)

크루스칼 알고리즘(Kruskal`s Algorithm)

최소 신장 트리(MST)를 찾는 알고리즘으로, 그래프의 모든 정점을 연결하는 데 사용된 간선들의 가중치 합을 최소화하는 트리를 찾음

1. 그리디 접근
   가중치가 작은 간선부터 선택하여 사이클을 형성하지 않도록 주의하며 트리를 구성

2. 시간복잡도
   -간선을 정렬하는데 O(E log E)의 시간이 필요. 여기서 E는 간선의 갯수
   -유니온 - 파인드(Union - Find) 연산은 거의 상수 시간에 수행되므로 O(E log V). 여기서 V는 정점의 갯수
   -총 시간 복잡도는 O(E log E). E가 V^2보다 작다면 O(E log V)로 간주할 수 있음.

그리디 알고리즘의 한계

1. 최적해를 보장하지 않는 경우
   모든 문제에 대해 항상 최적해를 보장하지 않음. 그리디 알고리즘이 최적해를 보장하는 문제를 탐욕적 부분 구조(Greedy Choice Property)를 가진다고 함

2. 복잡한 문제
   일부 문제에서는 그리디 접근이 적합하지 않을 수 있으며, 동적 프로그래밍이나 백트래킹 등의 다른 알고리즘이 필요할 수 있음