그리디 알고리즘(Greedy Algorithm)

서론

---

  그리디란 무엇이고 어떻게 적용하는지 간단히 정리하고자 합니다.

 

출처 : 나무위키 그리디

그리디 알고리즘

  코딩 테스트를 준비하면서 예전에 공부했던 그리디 알고리즘을 정리하면서 공부하고자 합니다.

 

1. 그리디 알고리즘이란?

그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법이다.

출처 : 나무위키

 

  그리디 알고리즘은 문제를 해결할 때 현재 단계에서 최선이라 생각되는 선택을 반복적으로 수행하여 최적의 해답에 도달하는 알고리즘입니다. 매 단계에서 최선을 선택하므로 탐욕 알고리즘이라고도 불립니다.

 

그리디 알고리즘은 매 순간 최선의 수를 선택하지만 그 수가 항상 최적의 해답을 보장하지 않습니다. 따라서 그리디 알고리즘을 사용하려면 문제의 특성을 잘 이해해야 합니다.

 

2. 그리디 알고리즘의 동작 원리

그리디 알고리즘은 다음과 같은 방식으로 동작합니다.

1. 현재 상테에서 최적의 수를 선택
2. 선택한 해를 기반으로 다음 단계를 진행
3. 이러한 과정을 반복하여 전체 문제를 해결

분할 정복과 비슷하게 작은 문제를 풀고 최종적으로 전체 문제를 푸는 방식으로 그리디 알고리즘은 지역적 최선의 선택이 전역적 최적 해답을 보장합니다.

 

3. 그리디 알고리즘의 조건

3.1 탐욕적 선택 속성 (Greedy Choice Property)

문제의 해결 과정에서 각 단계에서 "현재 시점에서 가장 좋은 선택"을 한다고 하더라도, 그 선택이 전체적으로 최적의 해결책을 보장할 수 있어야 합니다. 즉, 현재 선택이 최적의 해를 만든다는 보장이 있어야 합니다.

 

3.2 최적 부분 구조 (Optimal Substructure)

문제를 해결하는 과정에서 문제를 더 작은 부분 문제로 나누어 해결할 수 있어야 합니다. 그리디 알고리즘은 주어진 문제를 작은 부분 문제로 나누어 각각을 독립적으로 해결한 후, 그 결과를 합쳐서 전체 문제의 최적 해를 구합니다.

 

4. 그리디 알고리즘 설계 방법

4.1 문제 분석 및 목표 정의

그리디 알고리즘을 적용하려면 문제에서 각 단계에서 "최적의 선택"을 할 필요가 있기 때문에 문제를 분석하여 이런 선택이 가능한지 확인해야하고 그리디 알고리즘은 목표를 달성하는데 사용되기 때문에 목표를 설정해야 합니다.

 

4.2 그리디 선택 속성(Greedy Choice Property) 파악

그리디 알고리즘은 각 단계에서 지역 최적해를 선택하는 방식이기 때문에 이 속성이 성립하는지 검토해야 합니다. 즉 그리디 알고리즘이 각 단계에서 내린 선택이 전체 문제에서 최적의 해결책을 만드는 보장이 있어야 합니다.

 

4.3 문제를 작은 부분 문제로 나누기

그리디 알고리즘은 일반적으로 문제를 작은 부분으로 나누어 각 부분 문제에서 최적의 선택을 한다면 이를 결합하여 문제를 해결할 수 있습니다. 따라서 부분 문제의 최적 해가 전체 최적 해를 이끌어 낸다는 특징이 있어야 합니다.

 

4.4 문제를 해결하는 선택 기준

각 단계에서 어떤 기준으로 선택할지 정의해야 합니다. 최소값인지 최대값인지 등의 명확한 기준을 세워야 매 단계에서 선택할 요소를 결정할 수 있습니다.

 

5. 그리디 알고리즘 예제

문제 : 거스름돈 문제

동전의 종류가 500원 100원 50원 10원일 때 최소 동전의 개수로 주어진 금액을 거슬러 주는 문제입니다.

 

해결 과정

1. 가장 큰 동전붙 최대한 많이 사용
2. 나머지 금액에 대해 반복

Java 코드

public class Greedy {
    public static void main(String[] args) {
        int[] coins = new int[] { 500, 100, 50, 10 };    // 동전의 종류
        int amount = 1260;  // 거스름돈
        int count = 0;      // 동전의 개수
        for (int coin : coins) {
            count += amount / coin;
            amount %= coin;
        }
        System.out.println("최소 동전의 개수 : " + count);
    }
}

 

6. 그리디 알고리즘의 장단점

장점

1. 구현이 간단하고 직관적
2. 재귀나 동적 계획법보다 계산 속도가 빠름
3. 적은 메모리 사용

단점

1. 문제의 특성에 따라 최적 해를 보장 못함
2. 탐욕적 선택 속성과 최적 부분 구조를 만족하는지 확인이 필요
3. 특정 문제에서는 동적 계획법과 같은 더 복잡한 알고리즘이 필요

 

7. 그리디 알고리즘과 다른 알고리즘 비교

특징	그리디 알고리즘	동적 계획법	브루트 포스
해결 방식	현재 단계에서 최선의 선택	부분 문제를 저장하여 중복 계산 방지	가능한 모든 경우를 시도
시간 효율성	빠름	비교적 느림	매우 느림
최적 해 보장 여부	문제에 따라 다름	항상 보장	항상 보장
적용 가능 문제	탐욕적 선택 속성과 최적 부분 구조를 만족해야 함	최적 부분 구조만 만족하면 됨	모든 문제에 적용 가능

 

8. 그리디 알고리즘의 활용 사례

1. 최소 신장 트리(MST) : 크루스칼 알고리즘, 프림 알고리즘
2. 다익스트라 알고리즘 : 단일 출발점 경로 문제
3. 허프만 코딩 : 데이터 압축 알고리즘
4. 스케줄링 문제 : 작업 스케줄 최적화
5. 거스름돈 문제 : 동전 개수 최소화