그리디 알고리즘(Greedy Algorithm)

1. 정의

그리디 알고리즘은 탐욕법이라고도 하며, "매 순간 가장 좋아 보이는 선택"을 하는 것이다. 

 

2. 구현

알고리즘의 전체적인 구현 틀은 "정렬-순회-선택"의 3단계로 구성

 

3. 조건 

• 탐욕적 선택 속성 : 앞의 선택이 뒤의 선택에 손해를 끼치면 안됨
• 최적 부분 구조 : 전체 문제의 최적해가 부분 문제의 최적해들로 구성
• 정렬 기준 : 무엇을 기준으로 정렬했을 때 최적의 해가 나오는지?

 

import java.util.*;

public class GreedyTemplate{
	public int solve(int[] data){
    	int result=0;
        
        // 1. 정렬 : 탐욕적 선택을 윟나 기준(가중치, 비용)에 따라 데이터 정렬
        // 그리디는 어떤 기준으로 정렬할 것인지가 아주 중요.
        Arrays.sort(data);
        
        //2. 순회 : 정렬된 데이터를 확인
        for(int i=0; i<data.length; i++){
        	if(isPossible(data[i]){
            	result+=data[i];
                upadateState(data[i]);
            }
          }
         return result;
        }
      }