그리디 알고리즘 (Greedy Algorithm)

그리디 알고리즘이란?

매 순간 현재의 기준으로 최선의 답을 선택해나가는 기법

 

빠르게 근사치를 계산할 수 있지만 결과적으로는 최적해가 아닐 수 있다.

 

그리디 알고리즘 적용 조건

•  탐욕적 선택 특성 (Greedy Choice Property)
  • 지금 선택이 다음 선택에 영향을 주지 않을 경우
•  최적 부분 구조 (Optimal Substructure) 
  • 전체 문제의 최적해는 부분 문제의 최적해로 이루어짐 

 

그리디 알고리즘 예제

• Activity Selection Problem

출처 : zero-base

import java.util.ArrayList;
import java.util.Collections;

class Activity {
    String name;
    int start;
    int end;

    public Activity(String name, int start, int end) {
        this.name = name;
        this.start = start;
        this.end = end;
    }
}

public class Main {
    public static void selectActivity(ArrayList<Activity> list) {
        // 종료시간 기준 오름차순 정렬
        Collections.sort(list,(x1,x2)-> x1.end-x2.end);

        int time = 0;

        for (Activity activity : list) {
            if (activity.start >= time) {
                System.out.println(activity.name);
                time = activity.end;

            }
        }
    }

    public static void main(String[] args) {
        // Test code
        ArrayList<Activity> list = new ArrayList<>();
        list.add(new Activity("A", 1, 5));
        list.add(new Activity("B", 4, 5));
        list.add(new Activity("C", 2, 3));
        list.add(new Activity("D", 4, 7));
        list.add(new Activity("E", 6, 10));
        selectActivity(list);
    }
}