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

그리디(Greedy)

---

1. 그리디(Greedy)

• 그리디는 탐욕스러운 또는 욕심이 많은이라는 뜻
• 그리디는 문제를 해결하는 데 있어 각 단계에서 가장 최적이라고 생각되는 선택을 하는 알고리즘
• 그리디로 문제를 해결하는 접근 방식은 전체적으로 최적의 해결책을 보장하지는 않지만, 많은 경우에 매우 좋은 근사해를 제공하거나, 특정 문제에서는 최적의 해결책을 제공할 수 있음

 

2. 그리디 알고리즘의 장단점

• 간단하고 구현이 용이
• 특정 문제에서는 최적의 해결책을 보장
• 일부 문제에서는 최적의 해결책을 보장하지 못함

 

3. 그리디 알고리즘 문제

3.1 거스름돈 문제 : 가장 적은 수의 동전으로 거스름돈을 주는 문제

public class GreedyExample {
	// 1. 거스름돈 문제
	// -가장 적은 수의 동전으로 거스름돈을 주는 문제
	public static int minCoins(int[] coins, int amount) {
		
		int count = 0;				// 동전 개수
		
		Arrays.sort(coins);			// 동전 금액을 오름차순으로 정렬
		
		for(int i = coins.length - 1; i >= 0; i--) {
			count += amount / coins[i];
			
			System.out.printf("%d 동전은 %d개 필요합니다.\n", coins[i], amount / coins[i]);
			
			amount %= coins[i];
		
		}
		
		System.out.println("총 사용한 동전의 개수 : " + count);
		
		return count;
		
	}
	
}

3.2 활동 선택 문제 : 최대한 많은 활동을 선택할 수 있는 활동의 최대 개수를 구하는 문제

public class GreedyExample {
	// 2. 활동 선택 문제
	//	- 최대한 많은 활동을 선택할 수 있는 활동의 최대 개수를 구하는 문제
	public static int maxActivities(int[][] activities) {
		int count = 1;
		
		// 1. 활동을 종료시간 기준으로 정렬
		Arrays.sort(activities, Comparator.comparingInt(values -> values[1]));

		
		// 2. 첫번째 활동을 선택
		int laststartTime = activities[0][0];
		int lastEndTime = activities[0][1];
		
		System.out.printf("활동 시작 시간 : %d, 활동 종료 시간 : %d \n", laststartTime, lastEndTime);
		
		// 3. 현재 선택된 활동 종료 시간 이후에 시작하는 활동이 없을 때가지 반복을 수행
		for(int i = 1; i < activities.length; i++) {
			if(lastEndTime <= activities[i][0]) {
				
				laststartTime = activities[i][0];
				lastEndTime = activities[i][1];
				
				System.out.printf("활동 시작 시간 : %d, 활동 종료 시간 : %d \n", laststartTime, lastEndTime);
				
				count++;
			}
		
		}
		
		return count;
	}
}