탐욕적인 알고리즘, 그리디 알고리즘은 현재 상태에서 볼 수 있는 선택지 중에 최선의 선택을 하는 알고리즘입니다.
그리디 알고리즘은 동적 계획법 dp 보다 구현하기 쉽고, 시간복잡도가 우수합니다.
But, 항상 최적의 해를 보장하지 못한다는 단점도 존재합니다.
따라서, 코딩테스트 에서 그리디 알고리즘을 사용하기 전에는 항상 그리디 알고리즘을 적용할 때의 논리 유무를 확실하게, 충분히 살펴보고 사용하여야 합니다.

그리디 알고리즘

최적해를 구하기 위해 사용되는 근시안적 방법으로, 각 단계마다 가장 최선의 선택을 하는 알고리즘이다.
즉, 각 단계에서는 지금 상황에서 가장 최선의 선택을 하여, 전체적으로도 최적해에 근사한 해를 도출한다.
예를 들어, 동전 거스름돈 문제를 해결하고자 한다면, 시간 복잡도가 작은 것부터 거슬러줄 동전을 선택하면서 거스름돈을 계속해서 줄여나가면 된다.
그러면 가장 적은 동전의 개수를 사용하여 거스름돈을 제공할 수 있다.
But, Greedy 알고리즘은 항상 최적해를 보장하는 것은 아니다.
따라서, 문제의 종류와 상황에 맞게 적용해야 한다는 것이 중요하다.

다시말해,
미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법입니다.
이렇게 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘입니다.
정말 탐욕스럽죠?

핵심 이론 & 수행과정

1. 문제 해결을 위한 최적해의 구조를 파악합니다.
2. 각 단계마다 탐욕적인 선택을 한다.
3. 그리디 선택들을 하나의 해결책으로 연결시킵니다.
4. 생성된 해결책이 유효한지 검사합니다.
5. 최적해가 아니면, 2~4 과정을 반복하여 최적해를 찾습니다.

정리하면,

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

시간 복잡도

Greedy 알고리즘의 시간 복잡도는 선택하는 기준에 따라 다르다.
예를 들어,
선택 기준이 각 단계에서 가장 작은 것을 선택하는 경우, 시간 복잡도는 O(nlogn)이다.
하지만, 선택 기준에 따라 시간 복잡도는 다르게 결정될 수 있다는 것이 Greedy 알고리즘의 특징이다.
시간 복잡도는 입력값의 크기 n에 따라 알고리즘 실행 시간이 어떻게 증가하는지를 나타낸다.
Greedy 알고리즘은 각 단계마다 가장 최선의 선택을 하여 전체적으로 최적해를 보장하지 않을 수 있다.

따라서, 입력값에 따라 최악의 경우 시간 복잡도가 나쁠 수 있다.
일반적으로 그리디 알고리즘은 O(nlogn) 또는 O(n) 시간 복잡도를 갖지만, 각각의 문제에 따라 다른 시간 복잡도를 가질 수 있다. 그러나, Greedy 알고리즘이 수행 가능한 경우, 다른 알고리즘에 비해 더욱 빠르고 간결하기 때문에 많이 활용되고 있다.

Code

그리디 알고리즘은 각 단계마다 지금 당장 가장 최선인 선택을 하는 알고리즘이기 때문에, 구현 방식이 문제에 따라서 다르게 됩니다.
아래 예시는 그냥 이런게 있구나, 라고 생각만 하면서 봐주시면 감사하겠습니다.

public static void coinChange(int[] coinTypes, int change) {
    Arrays.sort(coinTypes); // 동전 종류를 오름차순으로 정렬한다
    int coinCount = 0;  // 거슬러줄 동전 수
    int i = coinTypes.length-1;  // coinTypes의 마지막 인덱스부터 탐색한다.
    while(change > 0) // 남은 거스름돈이 있는 동안 반복한다.
    {
        if(coinTypes[i] > change) {
            i--;  // 거스름돈보다 큰 동전은 제외하고, 다음 동전으로 이동한다.
        } else {
            change -= coinTypes[i];
            coinCount++; // 해당 동전으로 거스름돈을 지불한다.
        }
    }
    System.out.println("최소 동전 개수 : " + coinCount);
}

지도를 통한 예시

최적 부분 구조를 좀 더 살펴보면 그림과 같이 설명할 수 있다.
서울에서 대구를 거쳐 부산까지 가는 최단 경로를 찾는다고 가정해보자.
그림에서 보듯이, 서울에서 대구까지 가는 경로는 3가지가 있으며, 부산까지도 마찬가지로 3가지 경로가 있다.
서울에서 부산까지 가는 최단 경로는 200km + 80km = 280km이다.
이 경로는 서울에서 대구까지 가는 최단 경로(200km)와 대구에서 부산까지 가는 최단 경로(80km)로 구성된다.

즉, 서울에서 대구를 거쳐 부산까지 가는 최단 경로는 각각의 부분 문제인

1. 서울에서 대구까지 가는 최단 경로 문제와
2. 대구에서 부산까지 가는 최단 경로 문제의 해결 방법의 합이다.

따라서 문제의 최적 해결 방법은 부분 문제에 대한 최적 해결 방법으로 구성된다.
이러한 구조를 최적 부분 구조라 한다.

이를 통해, 그리디 알고리즘은 100% 최적해를 보장해주지 않는다. 다만, 어느 정도 적합한 수준의 해답을 알려준다.
따라서, 최적이 아닌 "되는가" 또는 "적당히 괜찮은 방법"을 찾을 때에는 사용할 수 있다.
특히, 계산속도가 정확한 알고리즘에 비해서 빠른 경우가 많기 때문에 실용적으로 사용이 가능하다.
허나 이게 정말로 "적당히" 괜찮은지에 대해서 알려면 정확한 증명이 수반될 수 있다.
또한, 해답을 찾아가는 과정에 있어서 그리디로 구한 값을 비교값으로 설정할 수가 있다.

참조*