Greedy Algorithms(탐욕법, 탐욕 알고리즘)

그리디 알고리즘 이란

Greedy Algorithm은 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다.

 

순간 순간마다의 최선의 결정이 전체 문제에서 최선의 해결책이 되지 않을 수 있다.

하지만 이러한 단점들을 극복하는 Greedy의 가장 큰 장점은 계산 속도에 있다. 그래서 Greedy 방법이 통하는 몇몇의 문제에서는 최적해를 빠르게 산출해낼 수 있다.

 

그리디 알고리즘 예제

모험가 길드 문제

모험가 길드장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로
구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했다.

 

N명의 모험가에 대한 정보가 주어졌을때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하라

 

• 2 3 1 2 2

import java.util.Arrays;
import java.util.Scanner;

// 모험가 길드 문제
public class GreedyTest4 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 길드 인원
        int n = sc.nextInt();

        // 길드인원 공포도
        int[] list = new int[n];
        for(int i = 0; i < n; i++){
            list[i] = sc.nextInt();
        }

        //공포도에 따라서 정렬
        Arrays.sort(list);

        // 특정 그룹에 속한 인원수
        int count = 0;
        // 그룹 수
        int group_count = 0;
        for(int i = 0; i < n; i++){
            // 특정 그룹에 인원 추가
            count +=1;

            // 특정 그룹의 인원이 해당 인원의 공포도와 같거나 크면 그룹결성
            if (count >= list[i]) {
                group_count +=1;
                count = 0;
            }
        }

        // 출력
        System.out.println("총 그룹 수: " + group_count);
    }
}