[알고리즘] 그리디 알고리즘(탐욕법)

Greedy(탐욕) 알고리즘이란 ?

Greedy를 번역하면 "탐욕스러운"이라는 뜻을 가집니다.

그리디 알고리즘은 탐욕이란 뜻처럼 현재 상황에서 최적의 해만을 선택합니다.

그리디는 현재 상황의 최적의 해를 구하는다는 것에 중점을 두어야하는데, 그 이유는 다음 그림을 봅시다.

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

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

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

 

그리디 알고리즘 적용 조건

1. 탐욕스러운 선택 조건

앞의 선택이 이후의 선택에 영향을 주지 않는다는 것으로 항상 안전하다는 것이 보장되어야 합니다.

 

2. 최적 부분 구조 조건

전체 문제에 대한 최적해가 부분 문제에 대해서도 최적해여야 합니다.

 

예제 코드

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

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

• 만약 거스름돈이 800원이라면, (500 x 1, 100 x 3) 500원 한개, 백원 3개로 총 4개의 동전을 줍니다.

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class greedy {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);

        System.out.println("물건의 가격을 입력 해주세요. : ");
        int price = input.nextInt();
        input.nextLine();

        System.out.println("지불할 금액을 입력해 주세요. : ");
        int giveMoney = input.nextInt();

        int changeMoney = price - giveMoney;
        exchangeCount(changeMoney);
    }

    private static int exchangeCount(int changeMoney) {
        int[] coin = new int[] {500, 100, 50, 10};
        List<Integer> coinArr = new ArrayList<>();
        int count = 0;

        System.out.println("거스름돈 : " + changeMoney);

        for (int i : coin) {
            count += changeMoney / i;
            coinArr.add(changeMoney / i);
            changeMoney %= i;
        }
        System.out.println("받은 동전 개수 배열 : " + coinArr);
        System.out.println("총 동전 개수 : " + count);
        return count;
    }
}

 

Greedy 알고리즘을 이용한 코딩 테스트 문제

[Java/자바] 프로그래머스 - 체육복/Greedy(탐욕법) 알고리즘

 

[Java/자바] 프로그래머스 Lv2 - 구명보트 (greedy 탐욕법)