그리디 알고리즘(Greedy Algorithm)

그리디 알고리즘은 "현재 상황에서 지금 당장 좋은 것만 고르는 방법"을 선택해 전체 적합한 결과를 도출하자는 알고리즘 기법입니다.
순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않습니다.
따라서 주어진 배열을 미리 정렬하여 좋은 것을 순회하는 방법으로 문제를 해결하기 때문에 정렬이 필요한 알고리즘입니다.

위의 예시와 같이 최초의 선택에서 최적 선택을 하여 부분 최적해는 구했지만 전체 선택에서는 오히려 최적이 아닌 경로를 선택하여 전체 문제에서의 최적값은 구하지 못하게 될 수 있습니다.

그리디 주요속성

그럼에도 불구하고 그리디 알고리즘은 속도가 매우 빠르기 때문에 자주 사용되는데, 이를 사용하기 위해서는 아래와 같이 2가지 조건을 만족해야 합니다.

1. 탐욕 선택 속성(Greedy Choice Property)

• 이전의 선택이 이후에 영향을 주지 않는다.

2. 최적 부분 구조(Optimal Substructure)

• 부분 문제의 최적결과가 전체에도 그대로 적용될 수 있어야 한다.
• 즉, 전체 문제를 작은 부분 문제로 나누어 각각의 부분 문제에서 최적의 해를 구한 후 이를 조합하여 전체 문제의 최적해를 구하는 것을 의미한다.

그리디 알고리즘 예시

public class Main
{
	public static void main(String[] args) {
	    Scanner scan = new Scanner(System.in);
	    int total = scan.nextInt();
	    int minCoinCnt = 0;
	    int coins[] = {500, 100, 50, 10};
	    
	    for (int coin : coins){
	        minCoinCnt += (total/coin);
	        total %= coin;
	    }
		
		System.out.println("result = " + minCoinCnt);
	}
}