[Algorithm 기초] 그리디 알고리즘

이진 탐색 ( Greedy Algorithm )

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

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

( 항상 최적의 값을 보장하는것이 아니라 최적의 값의 ‘근사한 값’을 목표로 함)

 

사용 로직 예 01

 

Activity Selection Problem

- 종료 시간 기준으로 정렬

- 먼저 종료되는 활동 순, 겹치지 안흐는 순으로 선택

 

적용조건

속도는 빠르지만 최적해를 보장하지 못함

- 탐욕적 선택 특성(Greedy choice property) - 지금 선택이 다음 선택에 영향을 주지 않는다.

- 최적 부분 구조(Optimal substructure) - 전체 문제의 최적해는 부분 문제의 최적해로 이루어진다.

 

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

//20240303 그리디알고리즘 - Activity Selection Problem
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 greedyPractice01 {
        public static void selectActivity(ArrayList<Activity> list){
            Collections.sort(list, (x1 , x2) -> x1.end - x2.end);
            int curTime = 0;
            ArrayList<Activity> result = new ArrayList<>();
            for (Activity item : list){
                if(curTime <= item.start){
                    curTime = item.end;
                    result.add(item);
                }
            }

            for (Activity item : result){
                System.out.print(item.name + " ");
            }
            System.out.println();
        }

        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);
        }
    }

 

 

 

 

관련 link

https://adjh54.tistory.com/212

[Java/알고리즘] 그리디 알고리즘(탐욕법, Greedy Algorithm) 이해하기

https://velog.io/@nana-moon/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%AC%EB%94%94Greedy-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

[알고리즘] 그리디(Greedy) 알고리즘