[Algorithm] 탐욕 알고리즘 (Greedy Algorithm)

탐욕 알고리즘 (Greedy Algorithm)

 

■ 정의

그림 1

그림 2

 

다음 그림에서 최댓값을 구하려면 그림1과 같이 5 + 7 + 9 = 21로 구할 것이다.

하지만 탐욕 알고리즘은 그 순간마다 최적의 선택을 하기 때문에 그림2와 같이 5 + 10 + 4 = 19를 구할 것이다. 

 

이처럼 탐욕 알고리즘은 지금 당장 좋은 것만을 고르며, 현재 선택이 나중에 미칠 영향은 고려하지 않는다. 따라서 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다.

 

따라서, 탐욕 알고리즘 해법은 그 정당성 분석이 중요하다. 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토한다.

 

거스름 돈, 활동 선택, 최소 신장 트리 문제들이 대표적이며, '가장 큰 순서대로', '가장 작은 순서대로' 등과 같은 기준을 제시해 준다.

 

 

■ 탐욕 알고리즘 조건

탐욕적 선택 속성 (greedy choice property): 탐욕적인 선택이 항상 안전하다는 것이 보장된다는 의미이다. 즉, 그리디한 선택이 언제나 최적해를 보장해야 한다.

최적 부분 구조 (optimal substructure): 부분 최적해들이 모여 전체 최적해를 구할 수 있는 경우이다. 즉, 전체 문제가 여러 부분 문제로 분할되며, 이 단계 하나하나에 대한 최적해가 도출되어야 한다는 의미이다.

 

■ Code(백준 No.11047) - 거스름 돈

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] coin = new int[N];

        for(int i = 0; i < N; i++){
            coin[i] = Integer.parseInt(br.readLine());
        }

        int cnt = 0;

        for(int i = N - 1; i >= 0; i--){
            if(coin[i] <= K){
                cnt += (K / coin[i]);
                K %= coin[i];
            }
        }
        System.out.println(cnt);
    }
}

 

■ 백준 No.11047

11047번: 동전 0