그리디 알고리즘

그리디 알고리즘

• 매 순간 현재 기준으로 최선의 답을 선택해 나가는 기법
  • 빠르게 근사치를 구할 수 있다.
  • 결과적으로는 최적해가 아닐 수도 있다.
• 예시

  • N개의 활동과 각 활동의 시작/종료 시간이 주어졌을 때, 한 사람이 최대한 많이 할 수 있는 활동의 수 구하기

    • 종료 시간 기준으로 정렬
    • 먼저 종료되는 활동 순, 겹치지 않는 순으로 선택
      
      

    public class Main{
    	public static void seletActivity(ArrayList<Activity> list){
        	Collections.sort(list, (x1,x2) -> x1.end - x2.end);
            
            int curTime = 0;
            ArrayList<Activity> result = new ArrayList<>();
            for(Activicy item : list){
            	if(curTime <= item.start){
                	curTime = item.end;
                    result.add(item);
                }
            }
            
            for(Activity item : result){
            	System.out.println(item.name + " ");
            }
        }
    }
    
    public static void main(String[] args){
    	ArrayList<Activity> list = new ArrayList<>();
        list.add(new Activity("A", 1, 5));
        .
        .
        .
        .
        selectActivity(list);
    }

  • 거스름돈

    • 큰 동전부터 계산

적용 조건

• 빠르지만 최적해를 보장하지는 못함
• 두 가지 조건에 해당하는 경우 적용 가능
  • 탐욕적 선택 특성 : 지금 선택이 다음 선택에 영향을 주지 않음
  • 최적 부분 구조 : 전체 문제의 최적해는 부분 문제의 최적해로 이루어짐

백준1541

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int sum = Integer.MAX_VALUE;

        String[] subtractions = input.nextLine().split("-");
        for(String subtraction : subtractions) {
            int temp = 0;
            String[] additions = subtraction.split("\\+");
            for(String addition : additions){
                temp += Integer.parseInt(addition);
            }

            if(sum==Integer.MAX_VALUE){
                sum = temp;
            }else{
                sum -= temp;
            }
        }
        System.out.println(sum);
    }
}