김태원 8월 특강 그리디

제로베이스 8월 기업 코테 라이브 특강 / 김태원

그리디 알고리즘 (Greedy Algorithm)

그리디 알고리즘은 탐욕 알고리즘이라고도 하며, 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최고의 상황만을 쫓아 최종적인 해답에 도달하는 방식입니다. 이 알고리즘은 전체 문제를 한 번에 해결하기보다는, 각 단계마다 지역적으로 최적의 선택을 하여 전체적인 최적해에 도달하는 것을 목표로 합니다.

예제 문제

문제: 일렬로 놓여 있는 숫자 카드에서 왼쪽 맨 끝과 오른쪽 맨 끝 카드 중 하나를 가져가는 방식으로 4개의 카드를 가져갔을 때 가져간 카드의 숫자 합의 최댓값을 구하세요.

카드 배열: [2, 3, 7, 1, 2, 1, 5]

그리디 알고리즘을 사용한 해결 방법:

1. 첫 번째 선택: 2와 5 중 더 큰 숫자인 5를 선택합니다.
2. 두 번째 선택: 2와 1 중 더 큰 숫자인 2를 선택합니다.
3. 세 번째 선택: 3과 1 중 더 큰 숫자인 3을 선택합니다.
4. 네 번째 선택: 7과 1 중 더 큰 숫자인 7을 선택합니다.

최종 결과: 선택한 카드들의 합은 5 + 2 + 3 + 7 = 17이 되어 최댓값이 됩니다.

최대 사과의 개수

여러 종류의 사과 박스가 있으며, 각 박스의 종류에 따라 박스에 담겨있는 사과의 개수가 다릅니다. 트럭에 박스를 실으려고 할 때, 트럭에 실을 수 있는 박스의 최대 개수 제한이 주어졌습니다. 이 프로그램은 트럭에 실을 수 있는 사과의 최대 개수를 반환합니다.

문제 설명

• box: 각 박스 종류의 정보를 담고 있는 2차원 배열입니다.
  • box[i][0]은 i 종류 박스의 개수
  • box[i][1]은 i 종류 박스 한 개에 들어 있는 사과의 개수를 나타냅니다.
• limit: 트럭이 실을 수 있는 박스의 최대 개수입니다.

이 프로그램은 트럭에 실을 수 있는 사과의 최대 개수를 계산합니다.

입출력 예

box	limit	answer
[[2, 20], [2, 10], [3, 15], [2, 30]]	5	115
[[1, 50], [2, 20], [3, 30], [2, 31], [5, 25]]	10	302
[[3, 40], [5, 20], [5, 70], [1, 80], [5, 30], [3, 35]]	15	745
[[2, 70], [5, 100], [3, 90], [1, 95]]	8	775
[[80, 20], [50, 10], [70, 15], [70, 30], [80, 70], [90, 88], [70, 75]]	500	23920

제한사항

• box의 길이는 100,000을 넘지 않습니다.
• box[i][0]은 i 종류 박스의 개수, box[i][1]은 i 종류의 박스 한 개에 들어 있는 사과의 개수입니다.
• 서로 다른 종류의 박스라도 담겨 있는 사과의 개수는 같을 수 있습니다.
• 1 <= box[i][0] <= 100
• 1 <= box[i][1] <= 100
• 1 <= limit <= 10,000,000

import java.util.*;
class Solution {
	public int solution(int[][] box, int limit){
		int answer = 0;
		Arrays.sort(box, (a, b) -> b[1] - a[1]);
		for(int[] x : box){
			int cnt = Math.min(x[0], limit);
			answer += cnt * x[1];
			limit -= cnt;
			if(limit == 0) break;
		}
		return answer;
	}

	public static void main(String[] args){
		Solution T = new Solution();
		System.out.println(T.solution(new int[][]{ {2, 20}, {2, 10}, {3, 15}, {2, 30} }, 5));
		System.out.println(T.solution(new int[][]{ {1, 50}, {2, 20}, {3, 30}, {2, 31}, {5, 25} }, 10));
		System.out.println(T.solution(new int[][]{ {3, 40}, {5, 20}, {5, 70}, {1, 80}, {5, 30}, {3, 35} }, 15));
		System.out.println(T.solution(new int[][]{ {2, 70}, {5, 100}, {3, 90}, {1, 95} }, 8));
		System.out.println(T.solution(new int[][]{ {80, 20}, {50, 10}, {70, 15}, {70, 30}, {80, 70}, {90, 88}, {70, 75} }, 500));
	}
}