[Algorithm] 그리디 알고리즘(탐욕법, greedy, Java) 알아보기

그리디 알고리즘이란❓

 

그리디 알고리즘이란 greedy라는 이름의 뜻에서 알 수 있듯이 탐욕스러운, 욕심스러운 알고리즘입니다.

 

탐욕이라는 뜻처럼 그리디 알고리즘(탐욕 알고리즘)은 각 단계에서 가장 최선의 선택을 하는 방법을 말합니다.

 

다음 그림을 보면 한눈에 알 수 있습니다.

0

가장 큰 수 탐색 greedy vs 일반

 

위 그림을 보면 가장 큰 수를 탐색하는 과정을 greedy 알고리즘과 일반적으로 탐색하는 과정을 보여줍니다.

 

가장 큰 수를 찾기 위해 앞으로 간다면 제일 큰 수가 있는 "99"과 연결되어 있는 3 ➡️ 99 을 생각할 것입니다.

 

하지만 Greedy 알고리즘은 시작부터 3과 12 두 수중 가장 큰 수인 "12"을 탐색하고 그다음 큰 수인 "6"을 탐색합니다.

 

이 처럼 그리드는 최종결과에서의 최적의 해가 아닌 "현재상황에서 최적의 해"를 구합니다.

 

즉  알고리즘은 현재 상황에서 가장 좋다고 생각되는 것을 선택해 나가면서 최종적인 해답을 구합니다.

 

그렇다면 여기서 의문점을 가질 것입니다.

 

그럼 최종적으로 가장 큰 수인 "99"가 아닌 "6"을 찾으니깐 잘못된 것 아닌가??

 

맞습니다. 그리디 알고리즘의 가장 중요한 점은 그리디 알고리즘은 문제를 해결하는 데 있어서 간단하고 빠르지만 순간의 최적의 선택을 한다고 해서 최종적인 해답이 최적이라는 보장이 없습니다.

 

그리디 알고리즘 조건

그리디 알고리즘을 적용하여 최적해를 구할 수 있는 문제는 다음과 같은 조건을 만족해야 합니다.

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

• 현재의 선택이 앞으로의 선택에 영향을 미치지 않고 최적해로 이어질 수 있어야 합니다.

2. 최적 부분 구조 (Optimal Substructure)

• 부분 문제의 최적해가 전체 문제의 최적해로 이어질 수 있어야 합니다.

3. 단항 선택 조건 (Unary Choice Condition)

• 매 단계마다 오직 하나의 선택만 가능해야 합니다.
• 각 단계에서 여러 선택지가 있는 경우 그중 하나를 선택하면 이후 단계에 영향을 미치지 않아야 합니다.

위 세 개의 조건을 충족한다면 그리디 알고리즘은 최적해를 보장합니다. 

 

 

 

 

그리디 알고리즘 단계

1. 선택 절차(Selection Procedure)

• 현재 상태에서의 최적의 해답을 선택한다.

2. 적절성 검사(Feasibility Check)

• 선택된 해가 문제의 조건을 만족하는지 검사한다.

3. 해답 검사(Solution Check)

• 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

 

대표 그리디 알고리즘 사례 : 거스름 돈

거스름돈은 대표적인 그리디 알고리즘의 사례입니다.

 

아래의 코드는 거스름돈을 거슬러 주는데 "500, 100, 50, 10" 4개의 동전을 사용해 최소한의 동전으로 거슬러 줄 수 있도록 합니다.

여기서 가장 동전 개수를 최소화해서 줄 수 있도록 하는 것은 "가장 큰 단위의 돈부터 주는 것"입니다.

 

package Bronze2;

import java.util.Scanner;

public class BOJ5585 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int pay = 1000 - sc.nextInt();
        int[] coins = {500, 100, 50, 10, 5, 1};
        int cnt = 0;


        for(int i = 0 ; i < coins.length; i++){
            if(pay % coins[i] >= 0){
                cnt += pay/coins[i];
                pay%=coins[i];
            }
        }
        System.out.println(cnt);
    }
}

 

그리디 알고리즘 장단점

장점

1. 단순성과 직관성
   • 그리디 알고리즘은 문제를 해결하는 데 있어 간단하고 직관적인 방법을 제공합니다.
   • 복잡한 논리나 많은 계산 없이도 문제를 해결할 수 있습니다.
2. 빠른 실행 시간
   • 일반적으로 그리디 알고리즘은 각 단계에서 최적의 선택을 하기 때문에, 비교적 적은 계산과 반복으로 문제를 해결할 수 있습니다.
   • 다른 복잡한 알고리즘에 비해 실행 시간이 짧은 편입니다.
3. 적은 메모리 사용
   • 그리디 알고리즘은 보통 현재의 선택만을 고려하므로, 메모리 사용량이 상대적으로 적습니다.
   • 동적 계획법이나 분할 정복법처럼 많은 중간 상태를 저장할 필요가 없습니다.
4. 부분 문제 독립성
   • 각 단계에서의 선택이 이후의 선택에 영향을 미치지 않기 때문에, 부분 문제를 독립적으로 해결할 수 있습니다.
   • 이로 인해 병렬 처리나 분산 계산에 유리할 수 있습니다.

---

단점

1. 최적해 보장 불가
   • 그리디 알고리즘은 항상 최적의 해를 보장하지 않습니다.
   • 특정 문제에서는 서브 최적해(부분적으로 최적화된 해)만을 제공할 수 있습니다.
2. 제약 조건의 중요성
   • 그리디 알고리즘이 올바르게 작동하려면 문제의 특정 조건이 충족되어야 합니다.
   • 이러한 조건이 만족되지 않는 문제에서는 그리디 알고리즘이 적절하지 않을 수 있습니다.
3. 복잡한 문제 해결 불가
   • 복잡한 최적화 문제나 다수의 제약 조건이 있는 문제에서는 그리디 알고리즘이 적합하지 않을 수 있습니다.
   • 예를 들어, 배낭 문제나 TSP(Traveling Salesman Problem)와 같은 문제에서는 다른 고급 알고리즘이 필요합니다.
4. 문제의 특성에 의존
   • 그리디 알고리즘은 문제의 특성에 따라 성능이 크게 좌우됩니다.
   • 동일한 문제라도 입력 데이터의 특성에 따라 알고리즘의 성능이 달라질 수 있습니다.

 

 

•